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

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

Постпатч

Пока все хорошо.Теперь для исправления последовательности Фибоначчи:

λ> 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