Haskell列表生成器

Question

我一直在处理涉及根据列表中的先前元素生成列表的问题(例如五边形数字).我似乎无法找到我想要的形式的内置函数.基本上,我正在寻找形式的功能:

([a] -> a) -> [a] -> [a]

当([a] -> a)发生名单至今并产生应该是在列表中的下一个元素a或者[a]是最初的名单.我尝试使用iterate来实现这一点,但是产生了一个列表列表,每个连续列表都有一个元素(所以要获得第3000个元素(list !! 3000) !! 3000)而不是list !! 3000.

Answer 1

如果重复依赖于先前术语的常数,则可以使用标准corecursion定义序列,就像使用fibonacci序列一样:

-- fibs(0) = 1
-- fibs(1) = 1
-- fibs(n+2) = fibs(n) + fibs(n+1)
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

-- foos(0) = -1
-- foos(1) = 0
-- foos(2) = 1
-- foos(n+3) = foos(n) - 2*foos(n+1) + foos(n+2)
foos = -1 : 0 : 1 : zipWith (+) foos 
                        (zipWith (+) 
                            (map (negate 2 *) (tail foos)) 
                            (tail $ tail foos))

虽然您可以引入一些自定义函数来使语法更好一些

(#) = flip drop
infixl 7 #
zipMinus = zipWith (-)
zipPlus  = zipWith (+)

-- foos(1) = 0
-- foos(2) = 1
-- foos(n+3) = foos(n) - 2*foos(n+1) + foos(n+2)
foos = -1 : 0 : 1 : ( ( foos # 0  `zipMinus` ((2*) <$> foos # 1) )
                                  `zipPlus`  foos # 2 )

但是,如果术语数量不同,那么您需要采用不同的方法.

例如,考虑p(n),给定正整数可以表示为正整数之和的方式的数量.

p(n)= p(n-1)+ p(n-2)-p(n-5)-p(n-7)+ p(n-12)+ p(n-15) - ...

我们可以更简单地定义为

p(n)= _Σk∈[1,n) q(k)p(nk)

哪里

-- q( i ) | i == (3k^2+5k)/2 = (-1) ^ k
--        | i == (3k^2+7k+2)/2 = (-1) ^ k
--        | otherwise         = 0
q = go id 1
  where go zs c = zs . zs . (c:) . zs . (c:) $ go ((0:) . zs) (negate c)

 ghci> take 15 $ zip [1..] q
 [(1,1),(2,1),(3,0),(4,0),(5,-1),(6,0),(7,-1),(8,0),(9,0),(10,0),(11,0),(12,1),
  (13,0),(14,0),(15,1)]

然后我们可以iterate用来定义p:

 p = map head $ iterate next [1]
   where next xs = sum (zipWith (*) q xs) : xs

注意如何iterate next创建一系列反向前缀,p以便于使用它q来计算下一个元素p.然后我们采用每个反向前缀的head元素来查找p.

ghci> next [1]
[1,1]
ghci> next it
[2,1,1]
ghci> next it
[3,2,1,1]
ghci> next it
[5,3,2,1,1]
ghci> next it
[7,5,3,2,1,1]
ghci> next it
[11,7,5,3,2,1,1]
ghci> next it
[15,11,7,5,3,2,1,1]
ghci> next it
[22,15,11,7,5,3,2,1,1]

将此抽象为模式,我们可以获得您正在寻找的功能:

construct :: ([a] -> a) -> [a] -> [a]
construct f = map head . iterate (\as -> f as : as)

p = construct (sum . zipWith (*) q) [1]

或者,如果我们定义一个辅助函数来生成列表的反向前缀,我们可以在标准的corecursive样式中执行此操作:

rInits :: [a] -> [[a]]
rInits = scanl (flip (:)) []

p = 1 : map (sum . zipWith (*) q) (tail $ rInits p)