Можно ли рекурсивно определить список в Haskell?

Question

В нескольких языках программирования (включая JavaScript, Python и Ruby) можно поместить список внутри себя, что может быть полезно при использовании списков для представления бесконечно подробных фракталов. Тем не менее, я попытался сделать это в Haskell, и он не работает, как я ожидал:

--aList!!0!!0!!1 should be 1, since aList is recursively defined: the first element of aList is aList. 
main = putStrLn $ show $ aList!!0!!0!!1 

aList = [aList, 1] 

Вместо печати 1, программа производства этой ошибки компилятора:

[1 of 1] Compiling Main    (prog.hs, prog.o) 

prog.hs:3:12: 
    Occurs check: cannot construct the infinite type: t0 = [t0] 
    In the expression: aList 
    In the expression: [aList, 1] 
    In an equation for `aList': aList = [aList, 1] 

Можно ли Погружает список внутри себя в Haskell, как я пытаюсь сделать здесь?

Answer 1

Нет, вы не можете. Во-первых, есть небольшая терминологическая путаница: у вас есть списки, а не массивы (which Haskell also has), хотя точка стоит в любом случае. Итак, как и все вещи Haskell, вы должны задать себе вопрос: Какой тип aList = [aList, 1] быть?

Рассмотрим более простой случай aList = [aList]. Мы знаем, что aList должен быть список что-то, поэтому aList :: [α] для некоего типа α. Что такое α? Как тип элементов списка, мы знаем, что α должен быть типом aList; то есть α ~ [α], где ~ представляет собой равенство типов. Итак, α ~ [α] ~ [[α]] ~ [[[α]]] ~ ⋯ ~ [⋯[α]⋯] ~ ⋯. Это, действительно, бесконечный тип, и Хаскелл запрещает такие вещи.

В случае значения aList = [aList, 1], у вас также есть ограничение, что 1 :: α, но все то, что позволяет нам сделать вывод, что должно быть Num α ограничение (Num α => [⋯[α]⋯]), что ничего не изменится.

---

Очевидные следующие три вопроса:

1. Почему Haskell списки содержат только один тип элемента?
2. Почему Haskell запрещает бесконечные типы?
3. Что я могу сделать по этому поводу?

Давайте рассмотрим их в порядке.

---

Номер один: Почему списки Haskell содержат только один тип элемента? Это из-за системы типа Хаскелла. Предположим, у вас есть список значений разных типов: [False,1,2.0,'c']. Каков тип функции someElement n = [False,1,2.0,'c'] !! n? Нет никого, потому что вы не могли знать, какой тип вы вернетесь. Так что же вы можете сделать с этой ценностью? В конце концов, вы ничего не знаете об этом!

---

Номер два: Почему Haskell запрещает бесконечные типы? Проблема с бесконечными типами заключается в том, что они не добавляют много возможностей (вы всегда можете обернуть их новым типом, см. Ниже), и они делают некоторые проверки подлинности ошибок. Например, in the question "Why does this Haskell code produce the ‘infinite type’ error?", несуществование бесконечных типов исключало ошибку с ошибкой intersperse (и даже без явной сигнатуры типа).

---

Номер три: Что я могу сделать по этому поводу? Если вы хотите подделать бесконечный тип в Haskell, вы должны использовать рекурсивный тип данных . Тип данных не позволяет типу иметь поистине бесконечное расширение, и очевидность избегает случайных ошибок, упомянутых выше. Таким образом, мы можем определить NewType для бесконечно вложенного списка выглядит следующим образом:

Prelude> newtype INL a = MkINL [INL a] deriving Show 
Prelude> let aList = MkINL [aList] 
Prelude> :t aList 
aList :: INL a 
Prelude> aList 
MkINL [MkINL [MkINL [MkINL ^CInterrupted. 

Это у нас наш бесконечно вложенный список, что мы хотели-печать это никогда не собирается прекращать, но ни один из типов были бесконечна. (INL a является изоморфными к [INL a], но это не равное к нему Если вам интересно об этом, разница между isorecursive types (what Haskell has) and equirecursive types (which allow infinite types)..)

Но обратите внимание, что этот тип не очень полезно; единственными содержащимися в нем списками являются либо бесконечно вложенные вещи, как aList, либо различные вложенные коллекции пустого списка. Там нет никакого способа, чтобы получить базовый случай значения типа a в одном из списков:

Prelude> MkINL [()] 

<interactive>:15:8: 
    Couldn't match expected type `INL a0' with actual type `()' 
    In the expression:() 
    In the first argument of `MkINL', namely `[()]' 
    In the expression: MkINL [()] 

Так что список вы хотите, это произвольно вложенный список. 99 Haskell Problems имеет вопрос о них, который требует определения нового типа данных:

data NestedList a = Elem a | List [NestedList a] 

Каждый элемент NestedList a является либо простым значением типа a, или список более NestedList a с. (Это то же самое, произвольно-ветвящегося дерева, которое сохраняет данные только в листьях.) Тогда у вас есть

Prelude> data NestedList a = Elem a | List [NestedList a] deriving Show 
Prelude> let aList = List [aList, Elem 1] 
Prelude> :t aList 
aList :: NestedList Integer 
Prelude> aList 
List [List [List [List ^CInterrupted. 

Вы должны определить свои собственные функции просмотра теперь, и обратите внимание, что, вероятно, тип NestedList a -> Int -> Maybe (NestedList a)-the Maybe предназначен для работы с целыми числами вне диапазона, но важная часть состоит в том, что он не может просто вернуть a. В конце концов, aList ! 0 не является целым числом!

Answer 2

Да. Если вам нужно значение, содержащее себя, вам понадобится тип, который содержит сам. Это не проблема; Например, вы могли бы выросли деревья, определены примерно как это в Data.Tree:

data Tree a = Node a [Tree a] 

Теперь мы можем написать:

recursiveTree = Node 1 [recursiveTree] 

Answer 3

Это невозможно с типом списка в Haskell, так как каждый элемент должен быть одного типа, но вы можете создать для него тип данных. Я не совсем уверен, почему вы хотите.

data Nested a 
    = Value a 
    | List [Nested a] 
    deriving (Eq, Show) 

nested :: Nested Int 
nested = List [nested, Value 1] 

(!) :: Nested a -> Int -> Nested a 
(!) (Value _) _ = undefined 
(!) (List xs) n = xs !! n 

main = print $ nested ! 0 ! 0 ! 1 

Это напечатает Value 1, и эта структура может быть полезной, но я предположил бы, что это довольно ограничено.

Answer 4

Было несколько ответов от «да, вы можете» на «нет, вы абсолютно не можете». Хорошо, оба правы, потому что все они затрагивают различные аспекты вашего вопроса.

Другой способ добавить «массив» к себе, разрешить список чего угодно.

{-# LANGUAGE ExistentialQuantification #-} 

data T = forall a. T a 
arr :: [T] 
arr = [T arr, T 1] 

Таким образом, это добавляет аранжировка к себе, но вы не можете делать ничего другого с ним, за исключением того, доказать, что это является допустимым конструкт и скомпилировать его.

Поскольку Haskell строго типизирован, доступ к элементам списка дает вам T, и вы можете извлечь содержащееся значение. Но каков тип этого значения? Это «forall a. A» - может быть любым типом, который по сути означает, что нет никаких функций, которые могут что-либо с ним делать, даже не печатать, потому что для этого потребуется функция, которая может преобразовать любой тип a в String. Обратите внимание, что это не относится к Haskell - даже в динамических языках проблема существует; нет способа выяснить тип arr !! 1, вы считаете, что это Int. Что делает Haskell отличным от этого другого языка, так это то, что он не позволяет вам использовать эту функцию, если вы не можете объяснить тип выражения.

Другие примеры здесь определяют индуктивные типы, что не совсем то, о чем вы просите, но они показывают сговорчивое отношение к саморегуляции.

---

А вот как вы могли бы на самом деле сделать разумный конструкт:

{-# LANGUAGE ExistentialQuantification #-} 

data T = forall a. Show a => T a 

instance Show T where -- this also makes Show [T], 
     -- because Show a => Show [a] is defined in standard library 
    show (T x) = show x 

arr :: [T] 
arr = [T arr, T 1] 

main = print $ arr !! 1 

Теперь внутреннее значение обернут T ограничивается быть любым экземпляром Show («осуществление Показать интерфейс» в объектно-ориентированном программировании parlance), поэтому вы можете, по крайней мере, распечатать содержимое списка.

Обратите внимание, что ранее мы не могли включить arr в себя только потому, что между a и [a] не было ничего общего. Но последний пример является допустимой конструкцией, как только вы можете определить, что является общей операцией, которую поддерживают все элементы в списке. Если вы можете определить такую ​​функцию для [T], вы можете включить arr в список самого себя - эта функция определяет то, что является общим для определенных видов a и [a].

Answer 5

Нет, мы могли бы эмулировать:

data ValueRef a = Ref | Value a deriving Show 

lref :: [ValueRef Int] 
lref = [Value 2, Ref, Value 1] 

getValue :: [ValueRef a] -> Int -> [ValueRef a] 
getValue lref index = case lref !! index of 
    Ref -> lref 
    a -> [a] 

и есть результаты:

>getValue lref 0 
[Value 2] 
>getValue lref 1 
[Value 2,Ref,Value 1] 

Конечно, мы могли бы повторно использовать Maybe a вместо ValueRef a