这个看似简单的Haskell程序（动态规划）的解释

Question

这是一个计算美元划分方式数量的程序。在这一行代码 c = a ++ zipWith (+) b c 之前，c并未声明，那我们如何能将b和c进行zip操作呢？（我是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

- Swair

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 处倒退 notches。

    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 ++))

- Will Ness

Answer 2

y = f y 等价于无限次函数应用：`y = f ( f ( f ( f (...

因此 c = a ++ (zipWith (+) b c) 等价于 c = a ++ (zipWith (+) b (a ++ (zipWith (+) b (...)))

- nponeccop

Answer 3

这是一种特别复杂的递归定义用法。'change'和'c'都是以自己为基础来定义的。

'change _' 是一个由整数组成的无限长单向链表。

'c' 也是一个由整数组成的无限长单向链表。

'a ++ ... ' 的第一个元素是什么？如果'a'不为空（这里因为传入change函数的列表中全部是正数，所以'a'不为空），那么它就是'a'的第一个元素。

实际上，在第一次change中，'a'的长度为1，然后是5，直到最后一个'a'的长度为50。

所以'c'的第一个元素（或者前几个元素）来自于'a'。然后，一旦'a'用尽，'c'的后续元素就来自于'zipWith (+) b c'。

现在，'b'和'c'都是由整数组成的无限长单向链表。

'b'的第一个元素来自于对'change _'的递归调用的'a'部分之后的部分。'c'的第一个部分是'a'部分。

假设'a'部分的长度为5，并将'a'命名为'p1'。

c = (5 elements of 'a', call this p1)
  ++ (5 elements of zipWith (+) p1 b, call this p2)
  ++ (5 elements of zipWith (+) p2 (drop 5 b), call this p3)
  ++ (5 elements of zipWith (+) p3 (drop 10 b) ++...

- Chris Kuklewicz