Войти
ФлеймФорумПрограммирование

Функциональщина, односвязные списки: обратный обход

Страницы: 1 2 3 Следующая »
#0
22:57, 26 апр 2010

Почему-то основной рабочей структурой данных в функциональных языках является односвязный список.
Т.е. вида e1 -> e2 -> e3 -> ... -> eN
Причем добавлять/удалять элементы можно только из головы списка. Такой себе стек, фактически.
Причем он за собой тянет алгоритмически жуткие решения в ситуациях, когда надо эти списки переворачивать/обходить в обратном порядке.
Это вообще нормально? Как с этим люди живут в реальных условиях?

#1
23:04, 26 апр 2010

Двусвязные списки при нынешних гигабайтах памяти это дикий overhead. Программисты в опасности.

#2
1:35, 27 апр 2010

> Двусвязные списки

Тут похоже говорят о недокументировaных возможностях языка Си, субскрайб.

#3
2:25, 27 апр 2010

revert( head : tail ) := revert ( tail ) + head
revert( empty ) := empty

Работает за линейное время.

#4
2:28, 27 апр 2010

rusk
> Двусвязные списки при нынешних гигабайтах памяти это дикий overhead. Программисты в опасности.
двухсвязный список, например, чаров, как занимал почти в два раза больше памяти, так и занимает. будь у тебя хоть террабайт памяти, он всё равно будет занимать в 9/5 раз больше.

#5
2:31, 27 апр 2010

reversePrint( head : tail ) := do { reversePrint( tail ); print( head); }
reversePrint( empty ) := do { }

Пока не понимаю где же ужасы.

#6
6:35, 27 апр 2010

  Может быть автор имел в виду LISP, или Prolog? Си вроде не функциональный язык.

#7
7:32, 27 апр 2010

ffinder
> Причем добавлять/удалять элементы можно только из головы списка. Такой себе
> стек, фактически.
> Причем он за собой тянет алгоритмически жуткие решения в ситуациях, когда надо
> эти списки переворачивать/обходить в обратном порядке.

В каких именно случаях? В некоторых ФЯП можно написать почти также, как в Си.

Если нужна O(1) вставка/замена (для элемента "в фокусе"), можно использовать zipper. Zipper для (непустого) списка очень прост (далее Haskell):

data Zipper a = Zipper [a] a [a]

-- сдвинуть точку "фокуса" вправо
right :: Zipper a -> Maybe (Zipper a)
right (Zipper l f (x:xs)) = Just (Zipper (f:l) x xs)
right _ = Nothing

-- сдвинуть точку "фокуса" влево
left :: Zipper a -> Maybe (Zipper a)
left (Zipper (x:xs) f r) = Just (Zipper xs x (f:r))
left _ = Nothing

-- замена O(1)
change :: a -> Zipper a -> Zipper a
change x (Zipper l f r) = Zipper l x r

-- вставка
insertLeft :: a -> Zipper a -> Zipper a
insertLeft x (Zipper l f r) = Zipper (x:l) f r

insertRight :: a -> Zipper a -> Zipper a
insertRight x (Zipper l f r) = Zipper l f (x:r)

Функции right/left можно, используя GADT, избавить от Maybe. :) Можно еще использовать линейные типы, и получить обычный код с мутацией в результате (но только не в Haskell).

Такой трюк используется, например, в XMonad.

ПРАВКА: добавил insertLeft/insertRight

#8
8:53, 27 апр 2010

>Почему-то основной рабочей структурой данных в функциональных языках является односвязный список.
Потому что они самые простые и быстрые

>Причем он за собой тянет алгоритмически жуткие решения в ситуациях, когда надо ЭТИ списки переворачивать/обходить в обратном порядке.
Если фя чистый, то ЭТО уже идеологически неверно, там нет деструктивных действий, мы создаем новый список.

Да и все равно проблем нет.

reverse [1,2,3]
foldl (\a b -> b:a) [] [3,2,1]
0:[1,2,3]
[1,2,3]++[4]
#9
9:53, 27 апр 2010

Suslik
> двухсвязный список, например, чаров, как занимал почти в два раза больше
> памяти, так и занимает. будь у тебя хоть террабайт памяти, он всё равно будет
> занимать в 9/5 раз больше.

Будет. Все зависит от объема используемых чаров, если у тебя гиг чаров, то естественно overhead дикий, а если на пару килобайт, тоже дикий, но не заметный, что им можно пренебречь.

#10
9:55, 27 апр 2010

разве нет в Haskell reverse для односвязных списков ?

#11
10:40, 27 апр 2010

Suslik
> двухсвязный список, например, чаров, как занимал почти в два раза больше
> памяти, так и занимает.
Есть ещё XOR списки.

#12
11:15, 27 апр 2010

id-alex
> revert
> Работает за линейное время.
непонятно зачем он вообще работает, если в двусвязном списке можно взять конечный элемент и идти в обратном направлении.

> Пока не понимаю где же ужасы.
DROnik
> мы создаем новый список.
вот они где.
т.е. зачем создавать промежуточный перевернутый список, когда нужно не создавать? а если список к тому же еще и длинный?

#13
11:16, 27 апр 2010

Suslik
> 9/5
3/2 или даже больше. Ты забыл про паддинг и алигнмент...

#14
11:21, 27 апр 2010

ffinder
> вот они где.
> т.е. зачем создавать промежуточный перевернутый список, когда нужно не
> создавать? а если список к тому же еще и длинный?

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

Страницы: 1 2 3 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.