haskell - 这个简单的haskell程序的解释(动态编程)

Question

这是计算分割一美元的方法数量的程序。我不明白这条线 c = a ++ zipWith (+) b c和之前一样，这行 c 没有在此之前声明，那么我们如何压缩 b 和 c？ (我是 Haskell 的新手，感谢一个很好的解释)

import Data.List
change [] = 1 : repeat 0
change (d : ds) = c where
  (a, b) = splitAt d (change ds)
  c = a ++ zipWith (+) b c
result = change [1, 5, 10, 15, 20, 25, 50] !! 100

Answer 1

change [] = 1 : repeat 0
change (d : ds) = c where
  (a, b) = splitAt d (change ds)
  c = a ++ zipWith (+) b c

然后，

result = (!! 100) $ xs 
  where 
    xs = change [1, 5, 10, 15, 20, 25, 50] 
       = let -- g = (\(a,b)-> fix ((a++) . zipWith (+) b)) 
             g (a,b) = let c = a ++ zipWith (+) b c in c
         in 
           g . splitAt 1 . change $ [5, 10, 15, 20, 25, 50]
         = g . splitAt 1 .
           g . splitAt 5 . change $ [10, 15, 20, 25, 50]
         = ....
         = let h n = g . splitAt n 
           in
             h 1 . h 5 . h 10 . h 15 . h 20 . h 25 . h 50 . (1:) . repeat $ 0

或者，更简单，

Prelude> (!! 100) $ foldr h (1:cycle [0]) [1, 5, 10, 15, 20, 25, 50]
1239

(这是一个正确的答案，顺便说一句)。这可以说更容易理解。您的问题因此被本地化为 g定义，

    g (a,b) = let c = a ++ zipWith (+) b c in c

Haskell 的定义是递归的(它们等价于 Scheme 的 letrec ，而不是 let )。

在这里它有效，因为当 c被懒惰地消耗，它的定义说它由两部分组成， a ++ ...所以首先 a被消耗。这是有效的，因为 a不依赖于 c .计算中 a不需要了解 c .

在 zipWith (+) b c , c本质上是一个 指针进入被定义的序列， length a槽口 返回 从生产点来看， rest ，在这次重写中:

    g (a,b) = 
      let c = a ++ rest
          rest = zipWith (+) b c
      in c

我们有 h n xs = g (splitAt n xs)然后这是描述输入列表与结果的总和，移动 n向前凹口:

    x1 x2 x3 x4 x5 x6 x7 x8 ................ xs     A
                   y1 y2 y3 y4 y5 .......... ys     B
    --------
    y1 y2 y3 y4 y5 y6 y7.................... ys == A + B

这表明 h可以用改进的访问位置重写，

change ds n = foldr h (1:cycle [0]) ds !! n  -- [1, 5, 10, 15, 20, 25, 50] 100
  where
    h n xs = ys where ys = zipWith (+) xs (replicate n 0 ++ ys)
        -- = fix (zipWith (+) xs . (replicate n 0 ++))