bankersqueue.hs

module BankersQueue where

data LenList a = LenList { len :: !Int, items :: [a] }
instance Monoid (LenList a) where
  mempty = LenList 0 []
  mappend (LenList n xs) (LenList m ys) =
    LenList (n+m) (xs++ys)

coh' :: LenList a -> Maybe (a, LenList a)
coh' (LenList _ []) = Nothing
coh' (LenList n (x:xs)) = Just (x, LenList (n-1) xs)

cons :: a -> LenList a -> LenList a
cons x (LenList n xs) = LenList (succ n) (x:xs)

rev :: LenList a -> LenList a
rev (LenList n xs) = LenList n (reverse xs)

data Queue a = Queue (LenList a) (LenList a)

empty :: Queue a
empty = Queue mempty mempty

mappendReverse' :: [a] -> [a] -> [a]
mappendReverse' xs ys = go xs ys []
  where
    go [] ys rs = reverse ys ++ rs
    go (x:xs) (y:ys) rs = x : go xs ys (y:rs)

mappendReverse :: LenList a -> LenList a -> LenList a
mappendReverse (LenList n xs) (LenList m ys) = LenList (n+m) (mappendReverse' xs ys)

mkQueue :: LenList a -> LenList a -> Queue a
mkQueue xs ys
  | len xs >= len ys = Queue xs ys
  | otherwise        = Queue (mappendReverse xs ys) mempty

coh :: Queue a -> Maybe (a, Queue a)
coh (Queue xss ys) = case coh' xss of
  Nothing -> Nothing
  Just (x, xs) -> Just (x, mkQueue xs ys)

append :: Queue a -> a -> Queue a
append (Queue xs ys) y = mkQueue xs (cons y ys)

Tja, es sind wohl doch nicht alle Haskell-Programme korrekt, die nur typchecken. 👅
In Zeile 14 wird x nicht verwendet, es muss

... = LenList (succ n) (x:xs)

heißen.

Und noch eine Sache, da weiß ich nicht, ob du es beabsichtigt hast:
mappendReverse' geht schief, wenn len xs > len ys. Das ist ja in mkQueue, wo mappendReverse nur verwendet wird, gerade ausgeschlossen. Aber mit

go xs [] rs = xs ++ rs

könnte man es einfach robuster machen, oder?