순전히 함수형 프로그래밍 언어의 이중 연결된 목록

Question

순수 함수형 언어로 이중 연결 목록을 만드는 방법은 무엇입니까? 즉, 여러분이 모나드에 있지 않은 Haskell과 같은 것으로서 여러분은 돌연변이가 없습니다. 가능한가? (독창적으로 링크 된 목록은 분명 꽤 쉽습니다.)

Answer 1

순수 함수형 언어에서 이중 연결 목록은 그다지 재미 있지 않습니다. 이중 연결된 목록의 개념은 노드를 움켜 잡고 어느 방향 으로든 갈 수 있거나 목록의 중간에 스플 라이스 할 수있게하는 것입니다.

• 당신의 왼쪽 또는 오른쪽 (변형 중 하나를 갈 수있는 중간에 포인터와

  단일 연결리스트 Huet의 : 순수한 functionaly 언어에서 당신은 아마이 두 데이터 구조를 하나 더 낫다 "지퍼")

• 랄프 힌즈 (Ralf Hinze)와 로스 패터슨 (Ross Paterson)이 발명 한 엄청난 데이터 구조의 손가락 트리입니다.

나는 지퍼의 큰 팬이다. 그것은 많은 상황에서 유용합니다.

Answer 2

여러 접근법이 있습니다.

이중 연결 목록을 생성 한 후에 돌연변이를 만들고 싶지 않으면 게으름에 의존하여 매듭을 묶을 수 있습니다. 진짜 기적을 사용하거나 - - 당신이 변경 가능한 이중 연결리스트를 원하는 경우

http://www.haskell.org/haskellwiki/Tying_the_Knot

어떻게 든 가짜 참조 할 필요가 일품에게 올렉 Kiseylov에 의해 제안 여기에 구현 된 트릭 :

http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html

을

흥미롭게도 전자는 근본적으로 성공하기 위해 게으름에 의존한다는 점에 유의하십시오. 궁극적으로 매듭을 묶기 위해 돌연변이 또는 게으름이 필요합니다.

Answer 3

나는 정확하게 당신이 이것을 위해 무엇을 필요로 하는가?라는 음악 팬의 질문을 반복합니다. 노먼 램지 (Norman Ramsey)는 다중 방향 순회가 필요한 경우 지퍼가 더 쉽다고 말합니다. 빠른 접합이 필요한 경우 손가락 나무가 잘 작동합니다. , 이중 연결리스트를 들어

type t = { a : t Lazy.t } 

let cycle n = 
    let rec start = {a = lazy (aux n) } 
    and aux = function 
    | 0 -> start 
    | n -> { a = lazy (aux (n-1))} 
    in start 

:

하지만, 단지 그것이 어떻게 보이는지 확인하기 위해 ...

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 

Answer 4

은 OCaml의에서 원형을 위해 간단하게 당신은 항상 그런 일을 할 수있는 목록을 연결 나는 비슷한 것을 할 수 있다고 상상한다. 그러나 타이핑과 관련하여 게으름과 친숙한 구조에 의존해야합니다. 빠르고 불필요한 순환 이중 연결 목록 :

type 'a t = { data : 'a; before : 'a t Lazy.t; after : 'a t Lazy.t } 

    let of_list l = 
    match l with [] -> assert false | hd::tl -> 
    let rec start = { data = hd; before = last; after = next } 
    and couple = lazy (aux (lazy start) hd) 
    and next = lazy (Lazy.force (fst (Lazy.force couple))) 
    and last = lazy (Lazy.force (snd (Lazy.force couple))) 
    and aux before = function 
    | [] -> (lazy start), before 
    | hd::tl -> let rec current = lazy { data = hd; before = before; after = after } 
        and couple = lazy (aux current tl) 
        and after = lazy (Lazy.force (fst (Lazy.force couple))) 
        and last = lazy (Lazy.force (snd (Lazy.force couple))) in 
        current, last 
    in start