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 Queue.elm (compressed) (123 downloads)

Leave a Reply