An Introduction to Elm Series: Solution to ‘Binary Tree’ example supplementary module ‘Queue’
In http://elm-lang.org/examples/binary-tree, we are given a basic implementation of a binary tree and we are asked to extend it in various ways.
One of the tasks asked us to traverse the tree in various ways, in order to implement the Breadth First Traversal we needed a Queue.
Following is the code that we used for the Queue that is based on this package http://package.elm-lang.org/packages/martinsk/elm-datastructures/2.0.0/Queue.
The solution that this module was used in can be found here http://bytefreaks.net/programming-2/elm/an-introduction-to-elm-series-solution-to-binary-tree-example under the -- Breadth-first section.
module Queue exposing (Queue, init, enqueue, dequeue, length, foldr, foldl, map, fromList, toList)
{-| This Module implements a simple LIFO queue
# Definition
@docs Queue
This is based on the
# Fundamentals
@docs init, enqueue, dequeue, length
# Usefull functions
@docs foldr, foldl, map, fromList, toList
-}
{-| a simple queue.
-}
type alias Queue a = (List a, List a)
{-| Creates an empty queue -}
init : Queue a
init = ([], [])
{-|Enqueue an element on a queue -}
enqueue : a -> Queue a -> Queue a
enqueue a (inqueue, outqueue) =
((a::inqueue), outqueue)
{-|Dequeues an element of the end of a queue, and also returns thel
element -}
dequeue : Queue a -> (Maybe a, Queue a)
dequeue (inqueue,outqueue) =
case outqueue of
[] ->
case inqueue of
[] -> (Nothing,(inqueue, outqueue))
(_::_) -> dequeue([], List.reverse inqueue)
(x::xs) ->
(Just x, (inqueue, xs))
{-| Get the length(number of elements) in the queue -}
length : Queue a -> Int
length (inqueue, outqueue) =
let
inqueue_len = List.length inqueue
outqueue_len = List.length outqueue
in
inqueue_len + outqueue_len
{-| Fold across a queue front ot back -}
foldr : ( a -> b -> b) -> b -> Queue a -> b
foldr f acc (inqueue, outqueue) =
List.foldl f (List.foldr f acc inqueue) outqueue
{-| Fold across a queue back ot front -}
foldl : ( a -> b -> b) -> b -> Queue a -> b
foldl f acc (inqueue, outqueue) =
List.foldr f (List.foldl f acc outqueue) inqueue
{-| maps from a queue of type a to a queue containing elements of type
b -}
map : (a -> b) -> Queue a -> Queue b
map f (inqueue, outqueue) =
(List.map f inqueue, List.map f outqueue)
{-| converts a queue into a list -}
fromList : List a -> Queue a
fromList l =
(l, [])
{-| converts a list into a queue -}
toList : Queue a -> List a
toList (inqueue, outqueue) =
inqueue ++ (List.reverse outqueue)
You can download the module from here [download id=”1835″]
