haskell - Haskellfoldrの計算手順

Question

haskellの「foldr」関数の使用手順を知っている人はいますか？

GHCIコマンドウィンドウ：

foldr (\x y -> 2*x + y) 4 [5,6,7] 

評価後の結果：

40

これに関する手順、

Prelude> foldr (\x y -> 2*x + y) 4 [5,6,7] 
6 * 2 + (7 * 2 + 4)
12 + 18 = 30
5 * 2 + 30 = 40 v

Answer 1

foldrの1つの定義は次のとおりです。

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f acc []     = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

Haskellのウィキブックスには、foldr（および他のfolds）に関する優れたグラフがあります。

  :                         f
 / \                       / \
a   :       foldr f acc   a   f
   / \    ------------->     / \
  b   :                     b   f
     / \                       / \
    c  []                     c   acc

つまりa : b : c : []（これは[a, b, c]）になります（これもf a (f b (f c acc))ウィキブックスから取得）。

したがって、あなたの例は次のように評価されますlet f = (\x y -> 2*x + y) in f 5 (f 6 (f 7 4))（簡潔にするためにのみlet-binding）。

Answer 2

実際に簡単に視覚化できます。

import Text.Printf

showOp f = f (printf "(%s op %s)") "0" ["1","2","3"]

それから

Main> showOp foldr
"(1 op (2 op (3 op 0)))"
Main> showOp foldl
"(((0 op 1) op 2) op 3)"
Main> showOp scanl
["0","(0 op 1)","((0 op 1) op 2)","(((0 op 1) op 2) op 3)"]

Answer 3

[これはデルナンの発言に対するコメントであるはずだったが、言葉が多すぎた...]

lambdabotユン、 ＃haskell ircでプライベートな「会話」を開くことができます（例： http ：//webchat.freenode.net/ ）。彼女は単純な反射能力を持っているので、意味のない文字を入力できます。

    Yoon: > foldr (\x y -> 2*x + y) o [a,b,c,d]
lamdabot: 2 * a + (2 * b + (2 * c + (2 * d + o)))

これは何が評価されるかを示していますが、Edkaが指摘しているように、評価の順序の写真は

     Yoon: > reverse (scanr (\x y -> 2*x + y) o [a,b,c,d])
lambdabot: [o,2 * d + o,2 * c + (2 * d + o),2 * b + (2 * c + (2 * d + o)),2 * a + (2 * b + (2 * c + (2 * d + o)))

、、、およびこの巧妙なデバイスfoldrで遊んでいるいくつかの良いレッスンを刻印したことを覚えています。foldlscanrscanl