Двунаправленный связанный список на языке чисто Функционального программирования
Mike корректен. Хвостовая рекурсия не оптимизирована компилятором Java или JVM. Вы будете всегда получать переполнение стека с чем-то вроде этого:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
3 ответа
In a pure functional language, a doubly-linked list is not that interesting. The idea of a doubly linked list is to be able to grab a node and go in either direction, or to be able to splice into the middle of a list. In a pure functionaly language you probably are better off with one of these two data structures:
A singly linked list with a pointer in the middle, from which you can go either left or right (a variant of Huet's "Zipper")
A finger tree, which is a mind-blowing data structure invented by Ralf Hinze and Ross Paterson.
I'm a big fan of the zipper; it's useful in a lot of situations.
Я бы повторил вопрос фаната музыки: "для чего именно вам это нужно?" Как отмечает Норман Рэмси: если вам нужен разнонаправленный обход, тогда молнии проще; Если вам нужно быстрое сращивание, хорошо подойдут деревья пальцев.
Но, чтобы посмотреть, как это выглядит ...
import Control.Arrow
import Data.List
data LNode a = LNode { here :: a, prev :: LList a, next :: LList a }
type LList a = Maybe (LNode a)
toList :: LList a -> [a]
toList = unfoldr $ fmap $ here &&& next
fromList :: [a] -> LList a
fromList l = head nodes where
nodes = scanr ((.) Just . uncurry LNode) Nothing $ zip l $ Nothing : nodes
append :: LList a -> LList a -> LList a
append = join Nothing where
join k (Just a) b = a' where
a' = Just $ a { prev = k, next = join a' (next a) b }
join k _ (Just b) = b' where
b' = Just $ b { prev = k, next = join b' Nothing (next b) }
join _ _ _ = Nothing
Там есть ряд подходов.
Если вы не хотите видоизменять двусвязный список после его создания, вы можете просто «связать себя узами брака», полагаясь на лень.
http://www.haskell.org/haskellwiki/Tying_the_Knot
Если вам нужен изменяемый двусвязный список, вам нужно как-то подделать ссылки - или использовать настоящие - как трюк, предложенный Олегом Кисейловым и реализовано здесь:
http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html
Интересно отметить, что первое основано на лени для преуспеть. В конце концов, чтобы связать себя узами брака, нужна мутация или лень.