module AssocList_Sol (
    Map, empty, insert, lookup, delete, keys,
    {- für Teilaufgabe 2 -} kvList, fold) where

import Prelude hiding (lookup)

newtype Map k v = AL [(k,v)]

empty :: Eq k => Map k v
empty = AL []

insert :: Eq k => k -> v -> Map k v -> Map k v
insert k v (AL al) = AL $ins al
  where
    ins [] = [(k,v)]
    ins ((k',v') : m)
        | k == k' = (k,v) : m
        | otherwise = (k',v') : ins m

lookup :: Eq k => k -> Map k v -> Maybe v
lookup k (AL al) = lo al
  where
    lo [] = Nothing
    lo ((k',v') : m)
        | k == k' = Just v'
        | otherwise = lo m

delete :: Eq k => k -> Map k v -> Map k v
delete k (AL al) = AL $ del al
  where
    del [] = []
    del ((k',v') : m)
        | k == k' = m
        | otherwise = (k',v') : del m

keys :: Eq k => Map k v -> [k]
keys (AL al) = map fst al

kvList :: Eq k => Map k v -> [(k,v)]
kvList (AL al) = al

fold :: Eq k => (k -> v -> a -> a) -> a -> Map k v -> a
fold f s (AL al) = foldr (\(k,v) -> f k v) s al