読者です 読者をやめる 読者になる 読者になる

IT練習ノート

IT関連で調べたこと(実際は嵌ったこと)を書いています。

foldlとfoldrの違い

Haskell

foldl 手続き型言語のループの代わり

foldr コンストラクタの置き換え

  • foldr
-- 型の確認
Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

-- リストのコンストラクタを適用
Prelude> :t foldr (:) []
foldr (:) [] :: Foldable t => t a -> [a]

-- identityの確認
Prelude> foldr (:) [] [1,2,3]
[1,2,3]
  • foldl
-- 型の確認
Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

-- リストのコンストラクタを適用
Prelude> :t foldl (:) []

<interactive>:1:7:
    Occurs check: cannot construct the infinite type: a ~ [a]
    Expected type: [a] -> [a] -> [a]
      Actual type: a -> [a] -> [a]
    In the first argument of ‘foldl’, namely ‘(:)’
    In the expression: foldl (:) []

-- identityの確認
Prelude> foldl (:) [] [1,2,3]

<interactive>:32:7:
    Occurs check: cannot construct the infinite type: a ~ [a]
    Expected type: [a] -> [a] -> [a]
      Actual type: a -> [a] -> [a]
    Relevant bindings include it :: [a] (bound at <interactive>:32:1)
    In the first argument of ‘foldl’, namely ‘(:)’
    In the expression: foldl (:) [] [1, 2, 3]
Prelude> 

http://data.tmorris.net/talks/list-folds/b30aa0fdff296c731bc5b1c824adf1d02b3b69d9/list-folds.pdf