Пояснение для этой простой поисковой программы haskell (динамическое программирование)

Question

Это программа, которая подсчитывает количество способов разделить один доллар. Я не понимаю строку c = a ++ zipWith (+) b c, так как перед этой строкой c не объявляется до этого, тогда как мы можем zip 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 ++)) 

Answer 2

y = f y эквивалентно бесконечной цепочке приложений: `у = F (F (F (F (...

так c = a ++ (zipWith (+) b c) эквивалентно c = a ++ (zipWith (+) b (a ++ (zipWith (+) b (...)))

Answer 3

Это особенно сложное использование рекурсивных определений. «c» определены сами по себе.

'change _' - бесконечно длинная односвязная линия ed списка Integer.

Этот «c» также является бесконечно длинным односвязным списком Integer.

Что является первым элементом «a ++ ...»? Если «a» не является пустым (и здесь он не пуст, так как список переходит к изменению, все положительные), то это первый элемент «a».

Фактически «a» имеет длину «1» в первом изменении, затем «5», затем «10», пока последний «a» не имеет длину «50».

Итак, первый элемент (ы) 'c' взяты из 'a'. Затем, как только они заканчиваются, следующие элементы «c» исходят из «zipWith (+) b c».

Теперь 'b' и 'c' являются бесконечно длинными односвязными списками Integer.

Первый элемент «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) ++...