Является ли бесконечная емкость списка встроенной в класс «Ord» или продукт определения числа haskell для числа?

Question

Я пытаюсь обернуть вокруг головы, как Haskell достигает бесконечные списки ... вот мой дорожный блок:

У вас есть список типов A и A реализует Ord класса типов. Вы можете описать пролет упорядоченных элементов, как так (intergers, например):

[1..6] 

, который приравнивает к ...

Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 (Empty)))))) 

Как бы Haskell знать, как построить бесконечный список? Может ли haskell создать бесконечный список любого типа данных, который поддерживает Ord?

Answer 1

Это может быть немного легче уйти от синтаксической-приторный [a..b] вещи, и думать о простой функции из Prelude:

repeat :: a -> [a] 
repeat x = x : repeat x 

Вы должны забыть об оценке сейчас и начать думать декларативно, т.е. думать выше, как функции в математике, который может быть прочитан:

«повторение х» означает «х» consed с «повторить х»

Да, «ленивая оценка» - это то, что мы называем тем, что позволяет нам это выразить, но в идеале нам бы хотелось просто забыть об оценке и подумать о том, что наш код означает. В обязательном программировании вы обязаны постоянно анализировать оценку.

Вот более или менее то, что ваши [1..] desugars к:

enumFrom n = n : enumFrom (succ n) 

и вы можете увидеть в ответ @ ТеЛ, как компилятор идет о расширении этого.

Answer 2

Haskell «создает» бесконечные списки, потому что он не создает никаких элементов, пока это не понадобится. Например, давайте рассмотрим расширение head [1..], которое приводит к 1 в Haskell и бесконечному циклу на строгих языках.

head [1..] 

===         [expand `head`, literally 
            just inline the definition] 
case [1..] of 
    []  -> error "empty list" 
    (x : xs) -> x 

===         [evaluate [1..] one step, 
            check if it matches the case] 
case 1:[2..] of 
    []  -> error "empty list" 
    (x : xs) -> x 

===         [it does!] 

(1 : [2..]) -> 1 

===         [fin] 

1 

Обратите внимание, что это довольно отсталой по сравнению с большинством языков, которые бы начать нападая определение [1..] вместо атаки head.

Вы можете написать [x..] не для любого типа в Ord (класс типов, которые только позволяет нам говорить о том, две вещи больше или меньше друг от друга), но вместо того, чтобы что-нибудь в Enum, как [x..] класса типов приводит к enumFrom x где enumFrom :: Enum a => a -> [a].

Answer 3

Концепция бесконечных списков должна быть легко понятна для всех, кто приходит с объектно-ориентированного фона.

Фокус в том, чтобы думать о списках Haskell не как массивы или даже связанные списки, а как объекты-итераторы. Объектом итератора является объект, который имеет два метода: hasNext и getNext.

Как правило, номер hasNext итератора возвращает False после конечного числа getNext выписок. Это, безусловно, верно, если вы считаете, что итераторы привязаны к «реальным» коллекциям, такие как массивы, хэш-карты, файлы и т. Д.

Но ничто изначально не заставляет итератор быть «конечным». Вы можете реализовать бесконечный итератор очень легко. В Haskell-подобный псевдокод:

object Iterator where 
    hasNext _ = True 
    getNext = do 
    state <- get 
    put (state + 1) 
    return state 

Если вы не знаете, как это итератор на самом деле реализуется, просто наблюдая за его поведением вы бы думать, что это связано с бесконечным (или, по крайней мере, очень большой) коллекции. Но это просто - объект, который возвращает последовательные числа.

Другая аналогичная аналогия - это специальные файлы в UNIX, такие как /dev/zero или /dev/random. Если бы они были привязаны к реальным файлам на вашем жестком диске, диск был бы бесконечным. Но они не являются - вместо этого содержимое генерируется по требованию ядром, и вы можете требовать столько, сколько захотите.

Нисходящие списки Haskell работают точно так же, за исключением того, что они также «буферизуют» все произведенные значения, так что вы можете их повторно исследовать без повторной оценки.