Я работаю над упражнением по программированию, цель которого состоит в том, чтобы написать функцию для получения термина в N-м индексе последовательности фигур Хофштадтера.
Вместо того, чтобы придумать базовое решение, используя формулу, я подумал, что будет интересной задачей создать бесконечный список для представления последовательности, а затем проиндексировать его.
Это был мой первоначальный подход, однако он зависает при попытке вычислить что-либо за пределами первых двух членов.
hof :: Int -> Int
hof = (!!) seqA
where
seqA = 1 : zipWith (+) seqA seqB
seqB = 2 : filter (`notElem` seqA) [3..]
seqA
обозначает последовательность терминов, а seqB
различия между ними.
Хотя я действительно не понимаю, как использовать seq
, я попытался использовать его, чтобы строго оценить термины, которые стоят перед желаемым, как показано ниже.
hof :: Int -> Int
hof 0 = 1
hof n = seq (hof $ n - 1) $ seqA !! n
where
seqA = 1 : zipWith (+) seqA seqB
seqB = 2 : filter (`notElem` seqA) [3..]
Это также зависает при попытке вычислить значения после первого индекса.
Поиграв в ghci, я нашел способ заставить это работать странным образом.
ghci> seqB = [2, 4, 5, 6]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> seqB = 2 : filter (`notElem` seqA) [3..]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> hof = (!!) seqA
Указав seqB
и начальное значение, а затем переопределив как seqA
, так и seqB
, кажется, что он работает нормально. Однако я заметил, что результат передачи больших значений в hof
, кажется, дает разные результаты в зависимости от того, сколько терминов я изначально поместил в список seqB
. Когда я переопределяю функцию в ghci, она по-прежнему использует старую версию для функций, которые вызывали ее до ее переопределения?
Я хотел бы знать, почему это работает в ghci и можно ли написать рабочую версию этого кода, используя подобную технику. Заранее спасибо!
Проблема в том, что seqA
бесконечно, и поэтому
(`notElem` seqA) x
никогда не может вернуть True. Если он увидит, что x
является первым элементом seqA
, тогда отлично: он может вернуть False. Но если он не видит x
, он хочет продолжить поиск: может быть, x
— следующий элемент! Список никогда не заканчивается, поэтому он никак не может сделать вывод, что x
определенно отсутствует.
Это классическая ошибка, которую совершают новички, пытаясь отфильтровать бесконечный список и ожидая, что список когда-нибудь закончится. Часто ответ состоит в том, чтобы использовать что-то вроде
x `notElem` (takeWhile (<= x) infList)
вместо. Таким образом, ваша программа перестанет искать x
, как только найдет число выше x
. Конечно, это работает, только если ваши списки отсортированы. Ваши уравнения выглядят так, как будто они создают восходящие списки, и в этом случае это сработает, но я не занимался алгеброй. Если ваши списки расположены не в порядке возрастания, вам нужно разработать какое-то другое условие остановки, чтобы избежать бесконечной рекурсии.
Другой ответ говорит вам о проблеме с вашим подходом и предлагает отличное решение. Я подумал, что было бы забавно попытаться разработать немного более эффективное решение; кажется позорным снова и снова проверять начало seqA
во время наших членских звонков. Вот идея, которая у меня возникла: смысл в том, чтобы seqB
было дополнением к seqA
, верно? А что, если мы просто определим функцию дополнения напрямую? Так:
complement :: Integer -> [Integer] -> [Integer]
complement = go 1 where
go i xs@(x:xt) = case compare i x of
LT -> i : go (i+1) xs
EQ -> i+1 : go (i+2) xt
GT -> go i xt -- this case should be impossible
go i [] = [i..] -- this case is irrelevant for our purposes
Дело EQ
немного подозрительно; это не работает для общих возрастающих входных последовательностей. (Но см. ниже.) В любом случае, с этим определением две последовательности могут быть определены вполне естественным образом:
seqA, seqB :: [Integer]
seqA = 1 : zipWith (+) seqA seqB
seqB = complement seqA
Попробуйте в ghci:
> take 10 seqA
[1,3,7,12,18,26,35,45,56,69]
Хороший. Теперь, если мы исправим случай EQ
, чтобы он работал правильно для всех (возрастающих) входных последовательностей, он должен выглядеть так:
complement :: Integer -> [Integer] -> [Integer]
complement = go i where
go i xs@(x:xt) = case compare i x of
LT -> i : go (i+1) xs
EQ -> go (i+1) xt
GT -> go i xt -- still impossible
go i [] = [i..] -- still irrelevant
К сожалению, наши определения seqA
и seqB
больше не работают. Правильное первое значение для seqB
зависит от того, находится ли 2
в seqA
, но то, находится ли 2
в seqA
, зависит от того, является ли первое значение seqB
1
или нет... К счастью, поскольку seqA
растет намного быстрее, чем seqB
, нам нужно только закрасить насос немного.
seqA, seqB :: [Integer]
seqA = 1 : 3 : 7 : zipWith (+) (drop 2 seqA) (drop 2 seqB)
seqB = complement seqA
-- OR
seqA = 1 : zipWith (+) seqA seqB
seqB = 2 : 4 : drop 2 (complement seqA)
Попробуйте в ghci:
> take 10 seqA
[1,3,7,12,18,26,35,45,56,69]
Определение seqX
немного менее естественно, но определение complement
немного более естественно, так что здесь, кажется, есть некий компромисс.
«Невозможный» случай вполне возможен, если вы можете придумать Integer
, который меньше 1. Конечно, здесь это не уместно, но кажется странным называть его невозможным, когда случай с пустым списком вызывается только как нерелевантный.
В качестве ответа на эту часть:
Когда я переопределяю функцию в ghci, она по-прежнему использует старую версию для функций, которые вызывали ее до ее переопределения?
Да, именно так это должно работать. Привязки в командной строке ghci не являются изменяемыми переменными, как в императивном языке, они должны работать так же, как переменные в любой другой части Haskell.
Итак, когда у вас есть это:
ghci> a = 1
ghci> b = [a]
ghci> b
[1]
a
— это просто имя для 1
, а b
— это просто имя для [1]
. Последнее было вычислено из выражения [a]
, увидев, какое значение a
было именем, но это абсолютно значение [1]
, а не выражение [a]
, на которое ссылается b
.
ghci> a = 2
ghci> b
[1]
Выполнение a = 2
не изменяет значение, на которое ссылается a
, оно просто изменяет состояние среды, доступное в приглашении ghci. Это не может повлиять на какие-либо значения, которые были рассчитаны, когда a
было именем для 1; они были и остаются чистыми ценностями.
Простой способ подумать об этом состоит в том, что a = 2
не «меняет a
», а просто вводит новую и отдельную привязку. Поскольку у него такое же имя, как и у существующего, новое имя затмевает старое, делая невозможным обращение к старому в любых будущих выражениях. Но в старом ничего не изменилось.
И вы фактически увидите точно такое же поведение в скомпилированном модуле в контекстах, где у вас может быть несколько привязок для одного имени (если вы затеняете аргумент функции с помощью let
или вкладываете let
s и т. д.). Все, кроме одного, будут недоступны, но то, что было определено в терминах теневого связывания, останется точно таким же; они не переоцениваются, как если бы они были определены в терминах новой привязки.
Имея это в виду, становится легко объяснить, почему это работает:
ghci> seqB = [2, 4, 5, 6]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> seqB = 2 : filter (`notElem` seqA) [3..]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> hof = (!!) seqA
Это почти то же самое, как если бы вы определили это следующим образом:
ghci> seqB_old = [2, 4, 5, 6]
ghci> seqA_old = 1 : zipWith (+) seqA_old seqB_old
ghci> seqB_new = 2 : filter (`notElem` seqA_old) [3..]
ghci> seqA_new = 1 : zipWith (+) seqA_new seqB_new
ghci> hof = (!!) seqA_new
seqB_old
это просто финте списокzipWith
останавливается на длине самого короткого списка, seqA_old
также является просто конечным списком, даже если он определен в терминах самого себя.seqB_new
— это бесконечный список, который просто должен фильтровать каждый элемент по любому из элементов конечного списка seqA_old
; это не связано с проблемой, на которую указывает Амаллой, но на самом деле это не тот список, который вы пытались определитьseqA_new
определяется с точки зрения самого себя, но seqB_new
было определено с точки зрения seqA_old
, а не этой новой версии. Взаимной рекурсии просто не происходит.Эта проблема на самом деле не поддается взаимно рекурсивному решению. filter
+ notElem
будут продолжать поиск за пределами того места, где они когда-либо могли бы вернуть результат, потому что они не могут использовать тот факт, что последовательность является строго возрастающей.
Вместо того, чтобы искать следующий элемент, который мы не видели, мы можем изменить проблему: начать с предположения, что мы увидим каждое число, и использовать delete
, чтобы удалить те числа, которые, как мы знаем, мы хотим исключить.
hof :: Int -> Int
hof = (!!) seqA
where
-- By definition, one is the cumulative sum of the other.
seqA = scanl' (+) 1 seqB
-- Iteratively build the sequence.
seqB = unfoldr (infinitely step) (1, [2 ..])
step c (d, xs) = (c, (c + d, delete (c + d) xs))
-- Helper for when ‘unfoldr’ is known to have
-- unbounded input (‘x : xs’ always matches)
-- and unbounded output (we always return ‘Just’).
infinitely f (d, x : xs) = Just (f x (d, xs))
@DanielWagner Я не думаю, что есть простой способ сделать это, поскольку
seqA
увеличивается быстрее, чемseqB
. Я полагаю, что список значений для проверки можно было бы где-то хранить как состояние, но, возможно, это еще менее чисто.