Okasaki notes

BankersQueue.hs

module BankersQueue where

import Prelude hiding (head, tail)

data Queue a =
  Queue [a] !Int [a] !Int
  deriving (Show)

empty :: Queue a
empty = Queue [] 0 [] 0

snoc :: Queue a -> a -> Queue a
snoc (Queue front lenF rear lenR) a = queue front lenF (a : rear) (lenR + 1)

(|>) :: Queue a -> a -> Queue a
(|>) = snoc

head :: Queue a -> Maybe a
head (Queue [] _ _ _) = Nothing
head (Queue (a:as) _ _ _) = Just a

tail :: Queue a -> Maybe (Queue a)
tail (Queue [] _ _ _) = Nothing
tail (Queue (_:as) lenF rear lenR) = Just $ queue as (lenF - 1) rear lenR

dequeue :: Queue a -> Maybe (a, Queue a)
dequeue q = (,) <$> head q <*> tail q

-- | Maintains front and rear element distribution
--
-- >>> empty
-- Queue [] 0 [] 0
-- >>> empty |> 'a'
-- Queue "a" 1 "" 0
-- >>> empty |> 'a' |> 'b'
-- Queue "a" 1 "b" 1
-- >>> empty |> 'a' |> 'b' |> 'c'
-- Queue "abc" 3 "" 0
-- >>> empty |> 'a' |> 'b' |> 'c' |> 'd'
-- Queue "abc" 3 "d" 1
-- >>> empty |> 'a' |> 'b' |> 'c' |> 'd' |> 'e'
-- Queue "abc" 3 "ed" 2
-- >>> empty |> 'a' |> 'b' |> 'c' |> 'd' |> 'e' |> 'f'
-- Queue "abc" 3 "fed" 3
-- >>> empty |> 'a' |> 'b' |> 'c' |> 'd' |> 'e' |> 'f' |> 'g'
-- Queue "abcdefg" 7 "" 0
--
queue :: [a] -> Int -> [a] -> Int -> Queue a
queue front lenF rear lenR
  | lenR <= lenF = Queue front lenF rear lenR
  | otherwise = Queue (front ++ reverse rear) (lenF + lenR) [] 0

-- | A note on when (reverse rear) runs:
--
-- $setup
-- >>> import Control.Monad
-- >>> import Control.Monad.Trans.Maybe
-- >>> :{
--  void $ runMaybeT $
--  foldr (<=<)
--    pure
--    (replicate 4 (\a -> MaybeT $ print a *> pure (tail a)))
--    (Queue "abc" 3 "def" 3)
-- :}
-- Queue "abc" 3 "def" 3
-- Queue "bcfed" 5 "" 0
-- Queue "cfed" 4 "" 0
-- Queue "fed" 3 "" 0
--
-- The "fed" string is created by reversing "def", but we don't _reach_ that
-- string until it gets to the front of the ... front :P. So that reverse
-- call on "def" wouldn't be executed until "fed" is at the front (the last
-- step there). Or at least that would be the case without printing it.