Shortest implementation of a linked list, stack and queue
Haskell, 81 69 characters
data L a=N|a:~L a
N~:z=z:~N
(a:~b)~:z=a:~(b~:z)
r N=N
r(a:~z)=r z~:a
This code makes use of no preexisting functions at all. The push operation is :~
, the enqueue operation is ~:
. Both pop and dequeue are via pattern match against :~
. The extra operation r
is reverse.
Stacks:
ex1 =
let stack0 = N -- empty stack
stack1 = 'a' :~ stack0 -- push 'a'
stack2 = 'b' :~ stack1 -- push 'b'
first :~ stack3 = stack2 -- pop
second :~ stack4 = stack3 -- pop
in mapM_ print [first, second]
—
λ: ex1
'b'
'a'
Queues:
ex2 =
let queue0 = N -- empty queue
queue1 = queue0 ~: 'x' -- enq 'x'
queue2 = queue1 ~: 'y' -- enq 'y'
queue3 = queue2 ~: 'z' -- enq 'z'
next0 :~ queue4 = queue3 -- deq
next1 :~ queue5 = queue4 -- deq
next2 :~ queue6 = queue5 -- deq
in mapM_ print [next0, next1, next2]
—
λ: ex2
'x'
'y'
'z'
List reverse operation:
ex3 =
let list = "alpha" :~ ("beta" :~ ("gamma" :~ N)) -- a list
tsil = r list -- reverse the list
native N = [] -- convert to native list
native (a:~z) = a : native z -- for easy printing
in mapM_ (print . native) [list, tsil]
—
λ: ex3
["alpha","beta","gamma"]
["gamma","beta","alpha"]