haskell-jp / questions #1

少なくともHackageのソースを見る限り https://hackage.haskell.org/package/bytestring-0.10.8.2/docs/src/Data.ByteString.html#local-6989586621679051445 、findEOFというローカル関数が "\n" かどうかしか見ていないのが直接的な原因ですね。で、ここで init で末尾の文字を取り除いた場合、改行コードが LF のみの環境では、末尾にある改行コードでない文字が削られてしまうので問題が起きます。
@naohaq ありがとうございます と言っても小生にはバグか仕様か分かりませんし どう対処すべきなのか不明なのですが まあ競プロなどにおいては いっそのこと Data.Text.IO.getLine に乗り換えるべきでしょうか? 使った事が無いのですが 充分に速いのでしょうか 試してみます
https://github.com/haskell/bytestring/issues/13 Issueが上がっていますが放置されているみたいですね…\rも取れるように変えられないか聞いてみます
Data.ByteString のinitとlastはO(1)で計算されるみたいなので、とりあえずのworkaroundとして last str が '\r' に等しかったら init str を、そうでなければ str を返す関数を書いておくのはどうでしょうか
とりあえずこんな関数を書いてみました。 https://gist.github.com/naohaq/b90edfa7308dd8db51314829d005df5e
import qualified Data.ByteString.Char8 as C

chomp :: C.ByteString -> C.ByteString
chomp str | C.length str < 1   = str
          | C.last str == '\r' = C.init str
          | otherwise = str
CRもLFもCRLFも取り除けるように直してみた。
chomp :: C.ByteString -> C.ByteString
chomp str = chompCRLF $ chompCRLF str
  where chompCRLF s =
          case C.unsnoc s of
            Nothing -> s
            Just (s_c, '\r') -> s_c
            Just (s_c, '\n') -> s_c
            Just _ -> s
log 2 x の整数部分だけが欲しくなることがよくあり、以下のようなコードを使うことが多いです。

log2Int :: Int -> Int
log2Int x = truncate $ logBase 2 $ fromIntegral x


計算が Int で閉じていて、速度が速い関数ってありますか?
fromIntegral と truncate が気に入らないとも言う。
Data.Bits の countLeadingZeros 使うのはどうですか? https://hackage.haskell.org/package/base-4.10.0.0/docs/Data-Bits.html#v:countLeadingZeros
logBase2 x = finiteBitSize x - 1 - countLeadingZeros x
@fumieval @naohaq Awesome, thank you much!
おー! ありがとう!
countLeadingZeros の Int 実装は clz# を呼んでますが、これって CPU 命令に翻訳されますか?
もしかして、自分で strings.h ffsll とかの FFI を定義しなくていい????
昔 ffsll が O(1) であること仮定したアルゴリズムを書いたことがあるんです。
素直に Data.Bits を使えばよかったのか?
とりあえずGHCのソースを見た感じだと、GHCのPrimitive Operation https://ghc.haskell.org/trac/ghc/wiki/Commentary/PrimOps として実装されているように見えます < clz#
__builtin_clz*() is supported by GCC and Clang
ということで、コンパイラに任されるようですね。
そういえば、整数値をF_2を係数体とする多項式だと思って剰余を取る関数を書こうとしたときに、WordとかIntだと最上位の0じゃないビットを探すのにcountLeadingZerosが使えるけどIntegerだと使えないのをどうしようかと悩んだんですけど、こういうの普通はどうするんですかね?
(追記)FiniteBits a とそうでない場合で実装を分けたいんだけど、という疑問です
log_2 の整数部分じゃだめですか?
直前のkazuさんの質問を参照されたしー
おっと、thread見てなかったです
リストから平衡二分木に変換するHaskell風のアルゴリズムがあれば教えてください。
ただし、ここでいう平衡二分木は、要素の数が2の累乗のとき、完全平衡になる二分木です。
左の部分木から詰めて行きます。
O(n)でできると思います。
スタックを使う命令的なアルゴリズムは知っています。
Data.Map.fromListでやっているようなこと、ということでしょうか?
あー、探索木ではありません。
リストに入っていた順に、底辺に要素が並べばいいです。
ぶっちゃけていうと、Merkleハッシュ木をリストから作りたいのです。
https://goo.gl/pYMBDr
mapAccumL とか使うのかな?
考える。
すみません、逆にこちらから教えていただきたいのですが、
ハッシュ木というのは、大量(あるいは大容量?)のハッシュ値を一本の木にまとめて空間効率を高める、みたいなイメージであってますか?
結局、型クラスを作って Integer と {Int, Word, Word64, Word32, Word16, Word8} に対するinstantiationを陽に記述しました
ハッシュ木の構造は
- 葉ノードが対象データのハッシュ値
- 中間ノードが、連結させた子のハッシュ値のハッシュ値
です。
ハッシュ木の性質の全容は掴んでないのですが、2つのデータ間の整合性を高速に検証するために使われるのが一般的だと思います。
僕が今取り組んでいるのは、Certificate Transparencyでして、これは世の中にある証明書すべてを書き込み系としては追加しかできないログに記録するという仕組みです。
読み出すことはできます。
このログにハッシュ木が使われています。
ユーザは、ハッシュ木の性質を使って、以下のことを高速に確かめられます。
- ある証明書がログの中に存在している
- ログが改ざんされてない
Chrome が Symantec が発行する証明書を信用しなくしようとしてますが、これは Symantec が www.google.com の証明書を間違って発行したことによります。
それを見つけた手段が CT です。
CT の仕様書である RFC 6962 って、結構酷かったんですが、改訂版は分かりやすくなっているし、具体的なアルゴリズムが載っているので、今実装して理解しようとしています。
こんな感じか:

import Data.Bits
import Data.List

data Tree a = Leaf a
            | Node (Tree a) (Tree a) deriving (Eq, Show)

singleton :: a -> Tree a
singleton = Leaf

join :: Tree a -> Tree a -> Tree a
join = Node

fromList :: [a] -> Tree a
fromList xs = reduce $ snd $ foldl' add (0,[]) $ map singleton xs
  where
    add (i,ts) t = (i+1, merge (mergeCount i) (t:ts))
    merge 0 ts        = ts
    merge n (t1:t2:ts) = merge (n - 1) (join t2 t1:ts)
    merge _ _ = error "merge"
    reduce [t] = t
    reduce (t1:t2:ts) = reduce (join t2 t1:ts)
    reduce _ = error "reduce"

mergeCount :: Int -> Int
mergeCount = countTrailingZeros . complement
これでどうでしょうか :sunglasses:

{-# LANGUAGE DeriveFoldable #-}
import Data.Foldable

data Tree a = Leaf a
            | Node (Tree a) (Tree a) deriving (Eq, Show, Foldable)

fromList :: [a] -> Tree a
fromList xs = case foldl' (flip $ push 0 . Leaf) [] xs of
  [] -> error "empty"
  [(_, r)] -> r
  ts -> error "incomplete"
  where
    push :: Int -> Tree a -> [(Int, Tree a)] -> [(Int, Tree a)]
    push m x ys'@((n, y) : ys)
      | m == n = push (m + 1) (Node y x) ys
      | otherwise = (m, x) : ys'
    push m x [] = [(m, x)]
ぱっと思いつくのは、
data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

fromList :: [a] -> Tree a
fromList [] = error "No Element"
fromList xs = construct (map Leaf xs)

construct :: [Tree a] -> Tree a
construct [t] = t
construct ts  = construct (pairing ts)

pairing :: [Tree a] -> [Tree a]
pairing (t:u:vs) = Node t u : pairing vs
pairing ts       = ts
@pogin has joined the channel
あー、なるほど。
言われてみると、簡単な話でしたね。> nobsun
fumieval くんもありがとう!
GHCのmissing-home-modules警告について教えてください。
cabalファイルにlibraryとexecutableがあって、executableの方がコンパイルされる際にlibraryで列挙しているモジュールを列挙せよと警告が出ます。
executableの依存関係に、そのlibraryを書いてあるので警告が出るべきではないと思うのですが。。。
モジュールを列挙せずに警告をなくすにはどうすればいいでしょうか?
なんだかさっと https://ghc.haskell.org/trac/ghc/ticket/13129 を読む限り、仕様通りの挙動じゃないように聞こえますね。。。 :sweat:
executableの方の other-modules に libraryのmoduleを列挙せよ、と警告してくるんですか?
なんとなくの推測ですがhs-source-dirsがデフォルトの.になっててexecutableがbuild-dependsに指定したライブラリではなく、ソースファイルを直接見に行ってるとかないですか?
cabal buildでlibとexeで同じモジュールを再コンパイルしていたら多分当たってます
@maoe ビンゴでした。
test のソースはディレクトリを分けないと、自分に依存できない問題と同じでした!
ありがとうございます。
質問です、Haskellにおいて余再帰とは末尾再起でない関数のことを指すのでしょうか?あと、この記事()で
そう、遅延評価だから、余再帰というテクニックが使える。
と書かれているのですが、遅延評価でないと余再帰は出来ないのでしょうか?
僕の理解では、入力が再帰構造を持っていて、関数がその構造を辿ると「再帰」と言います。つまり、[a] -> b みたいな関数を再帰と言っています。
余再帰はその逆で、a -> [b] のように出力が再帰的な構造を持つ場合に使います。
mapは再帰かつ余再帰です。
関数が無限のリストを生成する場合、正格評価だと手に負えませんが、遅延評価なら出力の消費者が制御できますね、ぐらいの意味でした。
通常は、ここでいう再帰も余再帰も区別せずに、再帰ということが多いです。
ありがとうございます!
@ohnabe has joined the channel