Haskell Length関数の実装

Question

私はHaskellプログラミングを学び始め、リスト構造体を理解しようとしています。したがって、 はリスト長関数を書きました。

myLength :: [a] -> Integer 
myLength = foldr (\x -> (+) 1) 0 

myLength1 :: [a] -> Integer 
myLength1 []  = 0 
myLength1 (x:xs) = (+1) (myLength1 xs) 

以上は2つの長さ関数です。私の質問は、どちらが良いですか？ 私自身の観点からは、myLength1ははるかに理解しやすく、 は操作リストに当てはまります。

しかしmyLengthが短く見え、再帰を使用しない、それは、myLength速い 実行を意味するものではないよりmyLength1

Answer 1

念頭にfoldrのこの "疑似実装" を取る：

foldr :: function -> initializer -> [a] -> b 
foldr _ i [] = i 
foldr f i (x:xs) = x `f` (foldr f i xs) 

今すぐあなたのコードがあります

myLength :: [a] -> Integer 
myLength = foldr (\x -> (+) 1) 0 

myLength1 :: [a] -> Integer 
myLength1 []  = 0 
myLength1 (x:xs) = (+1) (myLength1 xs) 

foldrも再帰的なので、myLength1とmyLengthはほぼ同じですが、最初のケースでは再帰呼び出しは自分で明示的にではなくfoldrで行います。彼らは同じ時間に実行する必要があります。

Answer 2

どちらの関数も同じことを行います。foldrは再帰を使用し、直接再帰関数と同様に実行を終了します。 foldrのバージョンがより洗練されていると主張することもできます（一度使い慣れたら、高次関数は直接再帰よりも読みやすくなります）。

しかし、これらの2つの機能はかなり悪いです。大量のメモリ（O（n）のスペース）をとり、評価が遅くなる大きなサンク（未評価の値）1 + (1 + (1 + ... + 0)..))を作成します。あなたがそうのように、リストの先頭から1秒の追加を開始すべきであることを避けるために：

は

betterLength xs = go 0 xs 
    where 
    go n [] = n 
    go n (_:xs) = n `seq` go (n+1) xs 

seqがgo関数が再帰的に呼ばれているので、+1の蓄積がない前に、nが評価されていることを保証します。折り目と、このバージョンを行うことも可能である

betterLength xs = go 0 xs 
    where 
    go n [] = n 
    go !n (_:xs) = go (n+1) xs 

：

betterLength = foldl' (\n _ -> n + 1) 0 

リットル EFTからfoldl'開始し、（厳密であるBangPatterns拡張子を使用すると、これを書くことができます'）。