I teach a data structures and algorithms course. Students can choose C++ or Java. As an exercise for myself, I am doing the assignments in Haskell. My primary goal is to understand what aspects of my class are easier in Haskell, and which aspects are more challenging. I am a fairly noob Haskell coder. Hence, I tend to be unaware of changes within the Haskell community, best practices, and "the right things". This is my secondary goal.
The class includes a List, Stack, Queue, Heap, and hash table. I'm up to the Queue structure so far.
For the List, I implemented
Semigroupto allow my List to be "list like" with the rest of Haskell's ecosystem, e.g.,
<>. Should I do that for the Queue too?
In the C++/Java version of the class we implement a doubly-linked list then apply a Stack Interface on top of it. This is to show the flexibility of the doubly-linked list structure. However for the Haskell version it seemed more prudent to express the Queue structure directly, i.e, a thing with a beginning and ending, with some stuff in the middle. Is this a good choice? Is there a better expression of the Queue structure?
pushstill constant time, i.e., O(1)? The recursive call for the More case will match either One or Two and be done.
head Nilis undefined. This is lame. While
head :: Queue a -> Maybe ais an option, is there a better option?
Is there a question I should have asked?
- A simple queue implementation in Haskell
- Uses Maybe which is a hint my implementation should as well.
- Derives Eq. That makes sense to compare two Queue's. I'll add that to mine.
Queue Data Structure
module Queue ( Queue (Nil, Unit, More), head, pop, push, fromList, empty, ) where import Data.List (foldl') import Prelude hiding (head) data Queue a = Nil | Unit a | Two a a | More a (Queue a) a deriving (Show) head :: Queue a -> a head Nil = undefined head (Unit x) = x head (Two _ x) = x head (More _ _ x) = x pop :: Queue a -> (Queue a, a) pop Nil = (Nil, undefined) pop (Unit x) = (Nil, x) pop (Two x y) = (Unit x, y) pop (More x middle y) = (More x middle' newEnd, y) where (middle', newEnd) = pop middle empty :: Queue a -> Bool empty Nil = True empty _ = False push :: a -> Queue a -> Queue a push x Nil = Unit x push x (Unit y) = Two x y push x (Two y z) = More x (Unit y) z push w (More x middle y) = More w (push x middle) y fromList :: [a] -> Queue a fromList = foldl' push' Nil where push' = flip push
module QueueSpec (spec) where import Data.Foldable (toList) import Data.List (sort) import Queue as Q import Test.Hspec import Test.Hspec.QuickCheck import Test.QuickCheck import Test.QuickCheck.Modifiers spec :: Spec spec = do describe "head" $ do it "put gets back" $ do Q.head (Unit 5) `shouldBe` 5 it "pop unit" $ do let x = Nil let x2 = push 5 x let (q, y) = pop x2 y `shouldBe` 5 it "pop more" $ do let x = Unit 1 let x2 = push 2 x let (q, y) = pop x2 y `shouldBe` 1 it "pop more with priority" $ do let x = Unit 2 let x2 = push 1 x let (q, y) = pop x2 y `shouldBe` 2 it "push a list" $ do let x = fromList [1, 2, 3, 4, 5] let (q, y) = pop x y `shouldBe` 1 it "first element of list is first of queue" $ property prop_firstListIsFirstQueue prop_firstListIsFirstQueue :: NonEmptyList Int -> Bool prop_firstListIsFirstQueue xs = Prelude.head l == Q.head q where l = getNonEmpty xs q = fromList l