Исправление рекурсивно определенного списка без << цикла >>

Question

контекст

Мы все знаем рекурсивно определенную последовательность Фибоначчи:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

λ> fibs
[1,1,2,3,5,9,13,21,34,55,89...

Вопрос

Я пытаюсь "залатать" его в нескольких местах, чтобы:

1. общее рекурсивное уравнение "элемент есть сумма двух предыдущих элементов" выполнено, но
2. могут быть исчисляемые исключения в отношении значений отдельных элементов.

Где я нахожусь

Полезность

Для этого я определю следующую функцию для изменения определенного элемента в списке:

patch :: Int -> a -> [a] -> [a]
patch i v xs = left ++ v : right where (left,_:right) = splitAt i xs

Я могу использовать это, чтобы изменить последовательность натуралов:

λ> patch 5 0 [0..]
[0,1,2,3,4,0,6,7,8,9...

Post-патч

Все идет нормально. Теперь для исправления последовательности Фибоначчи:

λ> patch 1 0 fibs
[1,0,2,3,5,8,13,21,34,55,89...

Это соответствует требованию (2).

Полный патч

Чтобы получить (1), я перепишу определение в более явном стиле "привязать узел":

fibs' p = rec where rec = p (1 : 1 : zipWith (+) rec (tail rec))

Без патча он все еще работает как положено:

λ> fibs' id
[1,1,2,3,5,9,13,21,34,55,89...

И теперь я могу исправить нужный элемент и сохранить рекурсивное определение:

λ> fibs' (patch 1 0)
[1,0,1,1,2,3,5,8,13,21,34...

ограничение

А можно я?

λ> fibs' (patch 5 0)
<<loop>>

проблема

В чем дело?

Интуитивно, поток данных кажется здоровым. Каждый элемент списка должен иметь правильное определение, которое не включает циклы. Я имею в виду, это было достаточно хорошо для без патчей fibs; исправление только должно сделать его более определенным.

Так что я, наверное, что-то упустил. Некоторая проблема строгости с моим patch функционировать? Некоторая проблема строгости в другом месте? Что-то еще целиком?

Answer 1

Ты немного строже, чем хотел бы быть. смотреть на

patch i v xs = left ++ v : right where (left,_:right) = splitAt i xs

Я полагаю, что вы намерены это xs гарантированно иметь по крайней мере i элементы. Но splitAt не знает этого Скорее всего, вы можете исправить вашу программу, используя свой собственный сплиттер.

splitAtGuaranteed :: Int -> [a] -> ([a], [a])
splitAtGuaranteed 0 xs = ([], xs)
splitAtGuaranteed n ~(x:xs) = first (x :) $ splitAtGuaranteed (n - 1) xs

редактировать

Даниэль Вагнер отмечает, что вам не нужна вся лень (или пристрастие) splitAtGuaranteed, Достаточно быть чуть-чуть ленивее:

patch i v xs = left ++ [v] ++ drop 1 right where (left, right) = splitAt i xs