4

This is the program which counts number of ways to partition one dollar. I don't understand the line c = a ++ zipWith (+) b c as before this line c is not declared before this then how can we zip b and c? (I'm new to haskell, a good explanation is appreciated)

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
4

3 回答 3

3 
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。

In 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 ++))
于 2013-08-11T13:10:11.703 回答
2

y = f y相当于无限的应用链：`y = f ( f ( f ( f (...

所以c = a ++ (zipWith (+) b c)等价于 c = a ++ (zipWith (+) b (a ++ (zipWith (+) b (...)))

于 2013-08-11T11:55:54.873 回答
2

这是递归定义的一个特别复杂的使用。“change”和“c”都是根据它们自己定义的。

'change _' 是一个无限长的 Integer 单链表。

这个 'c' 也是无限长的 Integer 单链表。

'a ++ ...' 的第一个元素是什么？如果 'a' 不为空（这里它不为空，因为列表传递给 change 都是正数），那么它是 'a' 的第一个元素。

事实上，“a”在第一次更改时的长度为“1”，然后是“5”，然后是“10”，直到最后一个“a”的长度为“50”。

所以'c'的第一个元素取自'a'。然后，一旦这些用完，“c”的以下元素就来自“zipWith (+) b c”。

现在 'b' 和 'c' 是无限长的 Integer 单链表。

'b' 的第一个元素来自在 'a' 部分之后对 'change_' 的递归调用的一部分。“c”的第一部分是“a”部分。

让 'a' 部分的长度减 5，并通过名称 'p1' 调用 'a'。

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) ++...
于 2013-08-11T11:57:43.487 回答