как в хаскеле реализованы списки?

ну ёлки-палки, ну Cons list же.. Stream

псевдокод:

data List = (:) a (List a) | Nil

при изменении обновляется голова, а хвост шарится.

При этом не факт, что у тебя во всех алгоритмах список вообще будет строиться, т.к. есть deforestification (он же list fusion основанный на foldr/build), ещё есть stream-fusion (продвинутый foldr/unfoldr).

Про ссылки на оптимизации можно почитать:

• «a short cut to deforestification» Andrew Gil, Johm Launchbury, Simon L Peyton Jones
• «Stream fusion» Duncan Coutts, Roman Leshchinskiy, Don Stewart
• диссер Coutts`а, это одна из последних работ и проблемы и бонусы предыдущих статей там описаны
• рассылку [Haskell-cafe] Stream fusion and span/break/group/init/tails там тоже хорошая подборка проблем и решений и подходов (ещё не реализованных)
• статьи SPJ про инлайнинг

оно тебя прям сейчас действительно надо?

Большинство серьезных вещей потребует вставку элементов в конец, а это гарантированная перестройка списка.

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

Мне было любопытно как это работает. Спасибо за развёрнутый ответ.

Оптимизации по типу ListBuffer из Scala или nconc из лиспа? Противоречит основным идеям хаскеля, но в некоторых случаях могут и оптимизировать.

Диванные эксперты подтянулись
!

Большинство серьезных вещей потребует вставку элементов в конец, а это гарантированная перестройка списка.

большинство серьёзных вещей могут использовать аккумулятор или вставку в голову и revert, так же они могут использовать DList, очереди и прочие структуры данных более подходящие под задачу. При этом очень большой класс алгоритмов может быть записан в форме foo = e : foo, в этом случае из-за ленивости операция будет стоить O(1), кстати с Text/ByteString такое не провернёшь нахаляву.

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

Примерно для: pattern-matching без view patterns, для алгоритмов где шарятся хвосты, для алгоритмов где реально строка не создается, может ещё какие классы алгоритмов я упустил, плюс в Prelude type String=[Char] и лень шевелиться, а Text нету в поставке с ghc (хотя имхо это плюс). Вообще сейчас есть Text, который выигрывает почти по всем пунктам, и bytestring + vector bytestring, который нужен там, где он нужен. Бесит когда в баиндингах стринги используют где попало.

извините за сбитый текст, если что не понятно, могу сформулировать по русски.

Большинство серьезных вещей потребует вставку элементов в конец, а это гарантированная перестройка списка.

Даже в ленивом языке? Вообще интересные вещи могут иметь место. Например, имея a :: [a], b :: [a] и с = a ++ b, конкатенации как таковой не произойдет, пока в коде не доберутся до определенной части списка C.

я думаю вопрос был в неявных оптимизациях этой структуры данных.

Обоснуй. На кой хер добавлять элементы в конец списка?

Большинство серьезных вещей потребует вставку элементов в конец, а это гарантированная перестройка списка.

DList?

Спасибо за ответ. Я даже не надеялся на такой конструктив в ответе на мой тупой вброс. Серьезно, спасибо=)

Например, имея a :: [a], b :: [a] и с = a ++ b, конкатенации как таковой не произойдет, пока в коде не доберутся до определенной части списка C

Зато он будет вынужден скопировать весь a в новый список, и лишь потом «пообещать» прибавить b. Или я ошибаюсь? Можно на пальцах объяснить как это будет представлено?

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

Рассмотрим реализацию через Prelude:

[]++ys=ys
(x:xs) ++ ys = x : (xs ++ ys)

let a = 1:2:3:Null
let b = 4:5:6:Null
let c = a ++ b = (++) (1:{2:..}) (4:{5:..}) =
      = 1: (++) ((++) (2:...) (4:...)) =
      /здесь 1 уже новый список остальное ссылки на старые старые/
      /то, что после : это отложенное вычисление/
      = далее раскручиваем список таким же образом, если он нам нужен.

можно попробовать в интерпретаторе:

Prelude Data.List Debug.HTrace> :m Data.List Debug.HTrace 
Prelude Data.List Debug.HTrace> let a = map (\x -> htrace ("<"++show x++">") x) [1..2]
-- htrace будет выводить значение x когда оно будет вычисляться
Prelude Data.List Debug.HTrace> let b = map (\x -> htrace ("<"++show x++">") x) [3..4]
Prelude Data.List Debug.HTrace> let c = a++b
-- на этом моменте у нас все списки в WHNF и ни один их элемент не вычислен, попробуем рассмотреть inits c
-- т.е. список голов списка c и посмотреть, когда вызываются вычисления

> inits c[br][/quote][[],[<1>
1],[1,<2>
2],[1,2,<3>
3],[1,2,3,<4>
4]]

тут мы видим когда в новом списке реально форсятся вычисления, для более полноценной картины надо бы написать свой ++ в доп дебагом, чтобы увидеть когда какой элемент форсится.

deforestification

а не deforestation? и не понятно, причем тут stream-fusion - отношение к списку довольно посредсвенное, или это политагитация?)

а не deforestation?

ты прав, я не прав.

и не понятно, причем тут stream-fusion - отношение к списку довольно посредсвенное, или это политагитация?)

хрен знает при чем, наверное показалось:

http://hackage.haskell.org/packages/archive/stream-fusion/0.1.2.5/doc/html/Da...

ну и перечисленные статьи тоже проливают свет на этот вопрос.

Недавно задавался похожими вопросами, но со стороны F#. Нашел интересный материал про реализацию структур данных в функциональном стиле http://en.wikibooks.org/wiki/F_Sharp_Programming/Advanced_Data_Structures

Про оптимизации должно быть что-то похожее на http://msdn.microsoft.com/ru-ru/magazine/ff714588.aspx

Для программиста списки в хаскеле иммутабельны.

Они мутабельны, хаскель же ленивый.

чем вставка элементов в конец принципиально отличается от присоединения элементов в начало?

Как понимать эту фразу?

Копированием списка.

может проще Окасаки почитать? А потом взять реализованные структуры с hackage.

Один дурак спросил, остальные отвечают.

1. В какой именно из реализация языка Хаскеля?

2. См. соотв. исходники.

может проще Окасаки почитать?

Посмотрел - мощная книга, надо будет прочитать, спасибо. Другой вопрос, что после императивных языков трудно уследить, что как работает. Экзешники или либы с F# программой можно хоть декомпилировать и, проведя аналогию с C#, понять, как это работает внутри.

Посмотрел - мощная книга, надо будет прочитать, спасибо. Другой вопрос, что после императивных языков трудно уследить, что как работает.

огромный плюс этой книги, что она объясняет весьма доходчиво, как работают структуры данных + там описан framework для исследования сложности ленивых алгоритмов + много ссылок на другие работы. Кстати есть тезисы из этой книги в свободном доступе, судя по беглому осмотру пары глав не сильно отличающиеся от книги.

Экзешники или либы с F# программой можно хоть декомпилировать и, проведя аналогию с C#, понять, как это работает внутри.

ну в случае hackage можно и исходники посмотреть, или я не понял сути.

можно пример реализиции хацкеля, в которой списки отличаются от

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

Кстати есть тезисы из этой книги в свободном доступе

Ага, это оказывается я не всю книгу нашел - сейчас посмотрел на амазоне - там страниц больше. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf. То есть получается это не вся книга полностью.

ну в случае hackage можно и исходники посмотреть, или я не понял сути

Все правильно - просто сейчас в коммерческой среде чаще применяются ФП языки, которые работают на виртуальных машинах, типа JVM и CLR, а это немного другая специфика, например, добавляются новые нюансы типа взаимодействия с Garbage Collector (кстати по ссылкам, что я оставлял вверху, утверждается, что паттерны ФП способствуют созданию именно короткоживущих объектов, которые без труда сносятся сборщиком) ну и просто для меня .net ближе, чем С :)

Тем, что при вставке в начало несколько разных списков могут разделять между собой один и тот же хвост(поскольку список односвязный). А вот вставка в конец приводит к тому, что шарить текущий список уже нельзя.

Видимо, имеется в виду, что по капотом изменяемость есть, иначе ленивость не реализовать.

То есть получается это не вся книга полностью.

не вся, но каждый раз когда всплывал вопрос о разнице ответ не находился (у меня-то бумажная).

а это немного другая специфика, например, добавляются новые нюансы типа взаимодействия с Garbage Collector

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

можно побольше подробностей

Чтобы лучше раскрыть свою идею, приведу в пример простой случай: реализация замыкания в C#.

public MyItem FindMyItem(List<MyItem> items, string itemName)
{
return items.Find(i => i.Name == itemName);
}

Как вы думаете, каким образом реализована эта конструкция внутри? А внутри создается анонимный класс, у которого создается поле, в котором хранится itemName и булевский метод, который проверяет имя на соответствие. Возникает еще вопрос - как долго этот анонимный класс будет храниться в памяти (представьте, что вместо строки itemName я передал словарь на гигабайт)? В данном случае - недолго будет храниться - но есть много других примеров, когда это может оказаться серьезной проблемой.

Я имел ввиду примерно такую специфику.

Так вот, в C# я хоть как-то представляю, что внутри творится - а на ФП языках мне пока страшно продакшн код писать :)

Ага, это оказывается я не всю книгу нашел - сейчас посмотрел на амазоне - там страниц больше.

На рутрекере есть.