1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import Control.Monad.Fix
import Data.IORef
import Prelude hiding (traverse)
data N a = N (IORef Bool, N a, a, N a)
newNode :: N a -> a -> N a -> IO (N a)
newNode b c f = do v <- newIORef False
return (N (v, b, c, f))
ll = mdo n0 <- newNode n3 0 n1
n1 <- newNode n0 1 n2
n2 <- newNode n1 2 n3
n3 <- newNode n2 3 n0
return n0
data Dir = F | B deriving Eq
traverse :: Dir -> N a -> IO [a]
traverse d (N (v, b, i, f)) =
do visited <- readIORef v
if visited
then return []
else do writeIORef v True
let next = if d == F then f else b
is <- traverse d next
return (i:is)
l2dll :: [a] -> IO (N a)
l2dll (x:xs) = mdo c <- newNode l x f
(f, l) <- l2dll' c xs
return c
l2dll' :: N a -> [a] -> IO (N a, N a)
l2dll' p [] = return (p, p)
l2dll' p (x:xs) = mdo c <- newNode p x f
(f, l) <- l2dll' c xs
return (c, l)
|
