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.
Questions
For the List, I implemented
Foldable,Functor,Monoid,Semigroupto allow my List to be "list like" with the rest of Haskell's ecosystem, e.g.,fmap, and<>. 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?
- Is
pushstill constant time, i.e., O(1)? The recursive call for the More case will match either One or Two and be done.
- Is
Errors.
head Nilis undefined. This is lame. Whilehead :: Queue a -> Maybe ais an option, is there a better option?Is there a question I should have asked?
Related Work
- 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
Tests
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
