LukaHorvat

{-# LANGUAGE ViewPatterns #-}
module Memo where

import Data.Bits (testBit, setBit, finiteBitSize)

data Memo a b = Fork (Memo a b) b (Memo a b)
    deriving Show

type Bit = Bool
newtype Bits = Bits [Bit]

LukaHorvat

fib :: Int -> Int
fib = memo fib'
    where fib' 0 = 1
          fib' 1 = 1
          fib' n = fib' (n - 1) + fib' (n - 2)

LukaHorvat

class Hashable a where
    hash :: Bits b => a -> b

instance Hashable Int where
    hash = id

LukaHorvat

type Graph = Vector [Int]

data BfsState = BfsState { queue :: Seq [Int]
                         , visited :: Set Int } 

pop :: MaybeT (State BfsState) [Int]
pop = do
    (x :< xs) <- viewl <$> gets queue
    modify $ \y -> y { queue = xs }
    return x

LukaHorvat

pop :: MaybeT (State BfsState) [Int]
pop = do
    (x :< xs) <- viewl <$> gets queue
    modify $ \y -> y { queue = xs }
    return x

push :: [Int] ->  MaybeT (State BfsState) ()
push x = do q <- gets queue
            modify $ \y -> y { queue = q |> x }

LukaHorvat

    No instance for (MonadState
                       (Seq (Maybe [Int]), Set Int)
                       (StateT (Seq Int, Set Int) Data.Functor.Identity.Identity))
      arising from a use of `gets'
    In the second argument of `(<$>)', namely `gets fst'
    In a stmt of a 'do' block: (x :< xs) <- viewl <$> gets fst
    In the expression:
      do { (x :< xs) <- viewl <$> gets fst;
           modify $ const xs *** id;

LukaHorvat

pop :: State (Seq Int, Set Int) (Maybe [Int])
pop = do
    (x :< xs) <- viewl <$> gets fst
    modify $ const xs *** id
    return x

LukaHorvat

pop :: State (Seq Int, Set Int) (Maybe [Int])
pop = do
    (x :< xs) <- viewl <$> gets fst
    modify $ const xs *** id
    return x

LukaHorvat

pacMan :: Int -> [Dependency] -> [Package]
pacMan n deps
    | outOfBounds         = error "Impossible to resolve"
    | Just xs <- try deps = xs ++ top xs
    | otherwise           = error "Impossible to resolve"
    where outOfBounds = any (> n) $ deps >>= (\(x, y) -> [x, y])
          try d | null d    = Just []
          try d = do
              let dependedOn = S.fromList $ map snd d
              let dependers  = S.fromList $ map fst d

LukaHorvat

mergesort :: Ord a => [a] -> [a]
mergesort []                       = []
mergesort [x]                      = [x]
mergesort (split -> (left, right)) = merge (mergesort left) (mergesort right) 
    where merge []       rs = rs
          merge ls       [] = ls
          merge (l : ls) (r : rs)
              | l < r     = l : merge ls (r : rs)
              | otherwise = r : merge (l : ls) rs