Skip to content

Instantly share code, notes, and snippets.

@ti1024
ti1024 / scheduling.md
Created November 3, 2014 02:01
Complexity of scheduling maintenance jobs so that the number of maintenance days is minimized

Here is how I would describe the problem in “Complexity of scheduling jobs on arcs in a network” by user thomas.


Complexity of scheduling maintenance jobs so that the number of maintenance days is minimized

There are three machines in a factory, and every day each machine can process at most one job. For each machine, we are given a list of jobs which have to be processed on that machine. Each job takes one day to complete. Each job j has release date rj and deadline dj, both integers and satisfying rjdj, meaning that job j must be processed on a day between rj and dj, inclusive.

Imagine that these jobs are maintenance jobs. If any of the machines is processing any of the jobs, the whole factory has to be closed for maintenance on that day. Therefore, we would like to schedule the job

@ti1024
ti1024 / Test.hs
Created September 4, 2012 21:28
Panic in GHC 7.4.1
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE UndecidableInstances #-}
module Test where
class C1 p q r | r -> p, r -> q
class C2 s
@ti1024
ti1024 / TestMTL.hs
Created September 3, 2012 18:53
Newtype deriving works as expected
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module TestMTL where
import Control.Monad.Reader.Class -- from mtl package
newtype MyIdentityT m a = MyIdentityT (m a)
deriving (Monad, MonadReader r) -- Compiles fine with GHC 7.4.1
{-
@ti1024
ti1024 / Test.hs
Created September 3, 2012 18:48
Newtype deriving does not work with a type class with an associated type synonym family
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module Test where
import Control.Monad.Reader.Class -- from monads-tf package
newtype MyIdentityT m a = MyIdentityT (m a)
deriving (Monad, MonadReader) -- GHC 7.4.1 reports an error on this line (see below)
{-
@ti1024
ti1024 / Test2.hs
Created September 3, 2012 05:14
Type family and higher-rank type with explicit type signature
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
module Test2 where
class C a b | b -> a
@ti1024
ti1024 / Test1.hs
Created September 3, 2012 05:12
Type family and higher-rank type
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
module Test1 where
class C a b | b -> a
@ti1024
ti1024 / gist:2554122
Created April 29, 2012 23:52
Happy example: attempt to add error handling 3
-- Calc.y
-- Based on http://www.haskell.org/happy/doc/html/sec-using.html
{
module Main (main) where
import Data.Char
}
%name calc
@ti1024
ti1024 / gist:2554044
Created April 29, 2012 23:40
Happy example: attempt to add error handling 2
-- Calc.y
-- Based on http://www.haskell.org/happy/doc/html/sec-using.html
{
module Main (main) where
import Data.Char
}
%name calc
@ti1024
ti1024 / gist:2554041
Created April 29, 2012 23:39
Happy example: attempt to add error handling 1
-- Calc.y
-- Based on http://www.haskell.org/happy/doc/html/sec-using.html
{
module Main (main) where
import Data.Char
}
%name calc
@ti1024
ti1024 / gist:2554028
Created April 29, 2012 23:34
Happy example
-- Calc.y
-- From http://www.haskell.org/happy/doc/html/sec-using.html
{
module Main (main) where
import Data.Char
}
%name calc