Возможный дубликат:
Как определить, бесконечен ли список?
В Haskell вы можете определить бесконечный список, например [1..]. Есть ли встроенная функция в Haskell, чтобы узнать, имеет ли список конечную длину? Я не думаю, что для этого можно написать функцию, предоставляемую пользователем, но внутреннее представление списков Haskell может поддерживать ее. Если не в стандартном Haskell, есть ли расширение, предоставляющее такую функцию?
Нет, это невозможно. Создать такую функцию было бы невозможно, потому что у вас могут быть списки, конечность которых может быть неизвестна: рассмотрим рекурсивный цикл, генерирующий список всех двойных чисел, которые он может найти, Или, чтобы следить за тем, что Даниэль Пратт упомянул в комментариях, вы можете иметь список всех шагов, которые выполняет универсальная машина Тьюринга во время ее выполнения, заканчивая список, когда машина останавливается. Затем вы можете просто проверить, бесконечен ли такой список, и решить проблему Halting!
Единственный вопрос, на который может ответить реализация, состоит в том, является ли список циклическим: если один из его хвостовых указателей указывает на предыдущую ячейку списка. Однако это специфично для реализации (Haskell не указывает ничего о том, как реализации должны представлять значения), нечистые (разные способы написания одного и того же списка дают разные ответы) и даже зависят от таких вещей, как список, который вы передаете такая функция еще была оценена. Даже тогда он все равно не сможет отличить конечные списки от бесконечных списков в общем случае!
(Я упоминаю об этом, потому что на многих языках (например, члены семейства Lisp) циклические списки являются единственным видом бесконечных списков, и нет способа выразить что-то вроде "списка всех целых чисел"., на этих языках вы можете проверить, является ли список конечным или нет.)
Нет никакого способа проверить конечность списков, кроме итерации по списку, для поиска окончательного [] в любой реализации, о которой я знаю. И вообще, невозможно определить, является ли список конечным или бесконечным, не идя в конечном счете (что, конечно, означает, что каждый раз, когда вы получаете ответ, который говорит конечный).
Вы можете написать тип оболочки вокруг списка, который отслеживает бесконечность и ограничивает себя только "разрешимыми" операциями (как-то похожее на NonEmpty, что позволяет избежать пустых списков):
import Control.Applicative
data List a = List (Maybe Int) [a]
infiniteList (List Nothing _) = true
infiniteList _ = false
emptyList = List (Just 0) []
singletonList x = List (Just 1) [x]
cycleList xs = List Nothing (cycle xs)
numbersFromList n = List Nothing [n..]
appendList (List sx xs) (List sy ys) = List ((+) <$> sx <*> sy) (xs ++ ys)
tailList (List s xs) = List (fmap pred s) (tail xs)
...
Как писал ehird, ваша единственная надежда состоит в том, чтобы выяснить, цикличен ли список. Способ сделать это - использовать расширение для Haskell, называемое "наблюдаемое разделение". См. Например: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053
Говоря о "внутреннем представлении списков", с точки зрения реализации Haskell нет бесконечных списков. "Список", о котором вы спрашиваете, на самом деле является описанием вычислительного процесса, а не объекта данных. Объект данных не бесконечен внутри компьютера. Такой вещи просто не существует.
Как уже говорили другие, внутренние данные списка могут быть циклическими, и реализация обычно сможет обнаружить это, имея концепцию равенства указателя. Но сам Хаскелл не имеет такой концепции.
Здесь используется общая функция Lisp для определения цикличности списка. cdr продвигается по списку на одну ступень, а cddr - на два. eq - предикат равенства указателя.
(defun is-cyclical (p)
(labels ((go (p q)
(if (not (null q))
(if (eq p q) t
(go (cdr p) (cddr q))))))
(go p (cdr p))))