Бесконечные списки, которые зависят друг от друга в Haskell?

Я работаю над упражнением по программированию, цель которого состоит в том, чтобы написать функцию для получения термина в 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 и можно ли написать рабочую версию этого кода, используя подобную технику. Заранее спасибо!

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
0
94
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Ответ принят как подходящий

Проблема в том, что seqA бесконечно, и поэтому

(`notElem` seqA) x

никогда не может вернуть True. Если он увидит, что x является первым элементом seqA, тогда отлично: он может вернуть False. Но если он не видит x, он хочет продолжить поиск: может быть, x — следующий элемент! Список никогда не заканчивается, поэтому он никак не может сделать вывод, что x определенно отсутствует.

Это классическая ошибка, которую совершают новички, пытаясь отфильтровать бесконечный список и ожидая, что список когда-нибудь закончится. Часто ответ состоит в том, чтобы использовать что-то вроде

x `notElem` (takeWhile (<= x) infList)

вместо. Таким образом, ваша программа перестанет искать x, как только найдет число выше x. Конечно, это работает, только если ваши списки отсортированы. Ваши уравнения выглядят так, как будто они создают восходящие списки, и в этом случае это сработает, но я не занимался алгеброй. Если ваши списки расположены не в порядке возрастания, вам нужно разработать какое-то другое условие остановки, чтобы избежать бесконечной рекурсии.

@DanielWagner Я не думаю, что есть простой способ сделать это, поскольку seqA увеличивается быстрее, чем seqB. Я полагаю, что список значений для проверки можно было бы где-то хранить как состояние, но, возможно, это еще менее чисто.

spectre256 10.02.2023 05:43

Другой ответ говорит вам о проблеме с вашим подходом и предлагает отличное решение. Я подумал, что было бы забавно попытаться разработать немного более эффективное решение; кажется позорным снова и снова проверять начало 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, зависит от того, является ли первое значение seqB1 или нет... К счастью, поскольку 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. Конечно, здесь это не уместно, но кажется странным называть его невозможным, когда случай с пустым списком вызывается только как нерелевантный.

amalloy 10.02.2023 08:27

В качестве ответа на эту часть:

Когда я переопределяю функцию в 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 или вкладываете lets и т. д.). Все, кроме одного, будут недоступны, но то, что было определено в терминах теневого связывания, останется точно таким же; они не переоцениваются, как если бы они были определены в терминах новой привязки.

Имея это в виду, становится легко объяснить, почему это работает:

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
  1. seqB_old это просто финте список
  2. Поскольку zipWith останавливается на длине самого короткого списка, seqA_old также является просто конечным списком, даже если он определен в терминах самого себя.
  3. seqB_new — это бесконечный список, который просто должен фильтровать каждый элемент по любому из элементов конечного списка seqA_old; это не связано с проблемой, на которую указывает Амаллой, но на самом деле это не тот список, который вы пытались определить
  4. 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))

Другие вопросы по теме