Генератор списка Haskell

Question

Я работал с проблемами (например, pentagonal numbers), которые включают в себя создание списка на основе предыдущих элементов в списке. Кажется, я не могу найти встроенную функцию формы, которую я хочу. По сути, я ищу для функции вида:

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

Где ([a] -> a) принимает список до сих пор и дает следующий элемент, который должен быть в списке и a или [a] является первоначальным списком. Я попытался использовать итерацию для достижения этого, но это дает список списков, каждый из которых имеет один дополнительный элемент (поэтому для получения 3000-го элемента я должен сделать (list !! 3000) !! 3000) вместо list !! 3000.

Answer 1

Если повторение зависит от постоянное число предыдущих, то вы можете определить серию с использованием стандартных корекурсия, как с последовательностью Фибоначчи:

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

Мы можем определить это более просто, как

р (п) = ∑ _{к ∈ [1, п)} д (к) р (п)

Где

-- 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 , Затем мы берем элемент заголовка каждого из этих обратных префиксов, чтобы найти 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)