Внутреннее представление списков Haskell?

Haskell поддерживает некоторые основные операции для рекурсии через списки, такие как head, tail, init и last. Мне интересно, как Haskell представляет данные списка? Если это односвязный список, то операции init и last могут стать дорогостоящими по мере роста списка. Если это двусвязный список, все четыре операции можно было бы сделать O(1) довольно легко, хотя и за счет некоторой памяти. В любом случае, мне важно знать, поэтому я могу написать соответствующий код. (хотя идеал функционального программирования, по-видимому, является одним из "спросить, что он делает, а не как он это делает" ).

Ответ 1

Списки представлены как... отдельные списки. Определение дается:

data [] a = [] | a : [a]

который вы могли бы написать как:

data List a = Empty | Cons a (List a)

Макет памяти полностью определяется этим.

Конструкторы представляют собой кучу
Внутренние полиморфные поля являются указателями на другие выделенные узлы.
Позвоночник ленив

Итак, вы получите что-то вроде этого:

So head есть O (1) в этой структуре, а last или (++) - O (n)

В Haskell нет магии для структур данных. Их прямолинейное определение полностью определяет, какова будет сложность (по модулю лень). Если вам нужна другая сложность, используйте другую структуру (например, IntMap, Sequence, HashMap, Vector и т.д.)...

Ответ 2

Списки Haskell односвязны, поэтому cons, head и tail являются O (1), а init и last равны O (n).

Если вам нужна более высокая производительность, рассмотрите возможность использования типа Seq из Data.Sequence, который обеспечивает O (1) доступ к обоим концам списка. Внутри он использует 2-3 дерева пальцев.