Haskell Prelude Crib Sheet

crib-sheet.hs

-----------
-- Types --
-----------

----
-- Builtin Types
----

-- Functions from `a` to `b`.
data a -> b
  id  :: a -> a
  ($) :: (a -> b) -> a -> b
  (.) :: (b -> c) -> (a -> b) -> a -> c

  instance Semigroup b => Semigroup (a -> b)
  instance Monoid b => Monoid (a -> b)

  instance Functor (a ->)
  instance Applicative (a ->)
  instance Monad (a ->)

-- 64-bit machine integers.
data Int
  instance Eq Int
  instance Ord Int
  instance Bounded Int
  instance Enum Int
  instance Show Int
  instance Read Int
  instance Num Int
  instance Real Int
  instance Integral Int

-- Arbitrary-size integers.
data Integer
  instance Eq Integer
  instance Ord Integer
  instance Enum Integer
  instance Show Integer
  instance Read Integer
  instance Num Integer
  instance Real Integer
  instance Integral Integer

-- 64-bit floating point numbers.
data Double
  instance Eq Double
  instance Ord Double
  instance Enum Double
  instance Show Double
  instance Read Double
  instance Num Double
  instance Floating Double
  instance Fractional Double
  instance Real Double
  instance RealFrac Double

-- Characters.
data Char
  instance Eq Char
  instance Ord Char
  instance Bounded Char
  instance Enum Char
  instance Show Char
  instance Read Char

-- Elements of another type that depend on input/output.
data IO a
  instance Semigroup a => Semigroup (IO a)
  instance Monoid a => Monoid (IO a)

  instance Functor IO
  instance Applicative IO
  instance Monad IO

----
-- Defined Types
----

-- A type with two elements. Useful for branching.
data Bool = False | True
  False     :: Bool
  True      :: Bool
  not       :: Bool -> Bool
  (&&)      :: Bool -> Bool -> Bool
  (||)      :: Bool -> Bool -> Bool
  otherwise :: Bool
  until     :: (a -> Bool) -> (a -> a) -> a -> a

  instance Eq Bool
  instance Ord Bool
  instance Bounded Bool
  instance Enum Bool
  instance Show Bool
  instance Read Bool

-- Ordered pairs of elements of two other types.
data (a, b) = (a, b)
  (,) :: a -> b -> (a, b)
  fst :: (a, b) -> a
  snd :: (a, b) -> b

  instance (Eq a, Eq b) => Eq (a, b)
  instance (Ord a, Ord b) => Ord (a, b)
  instance (Bounded a, Bounded b) => Bounded (a, b)
  instance (Show a, Show b) => Show (a, b)
  instance (Read a, Read b) => Read (a, b)
  instance (Semigroup a, Semigroup b) => Semigroup (a, b)
  instance (Monoid a, Monoid b) => Monoid (a, b)

  instance Functor (a,)
  instance Foldable (a,)
  instance Traversable (a,)
  instance Monoid a => Applicative (a,)
  instance Monoid a => Monad (a,)

-- Lists of elements of another type.
data [a] = [] | a : [a]
  []        :: [a]
  (:)       :: a -> [a] -> [a]
  head      :: [a] -> a        -- PARTIAL: fails on []
  tail      :: [a] -> [a]      -- PARTIAL: fails on []
  init      :: [a] -> [a]      -- PARTIAL: fails on []
  last      :: [a] -> a        -- PARTIAL: fails on []
  (!!)      :: [a] -> Int -> a -- PARTIAL: fails if index is too big
  (++)      :: [a] -> [a] -> [a]
  drop      :: Int -> [a] -> [a]
  dropWhile :: (a -> Bool) -> [a] -> [a]
  take      :: Int -> [a] -> [a]
  takeWhile :: (a -> Bool) -> [a] -> [a]
  reverse   :: [a] -> [a]
  repeat    :: a -> [a]
  replicate :: Int -> a -> [a]
  iterate   :: (a -> a) -> a -> [a]
  cycle     :: [a] -> [a]
  filter    :: (a -> Bool) -> [a] -> [a]
  map       :: (a -> b) -> [a] -> [b]
  zip       :: [a] -> [b] -> [(a, b)]
  unzip     :: [(a, b)] -> ([a], [b])
  break     :: (a -> Bool) -> [a] -> ([a], [a])
  splitAt   :: Int -> [a] -> ([a], [a])

  instance Semigroup [a]
  instance Monoid [a]
  instance Eq a => Eq [a]
  instance Ord a => Ord [a]
  instance Show a => Show [a]
  instance Read a => Read [a]

  instance Functor []
  instance Applicative []
  instance Monad []
  instance Foldable []
  instance Traversable []

-- Either an element of one type or nothing.
-- Useful for branching and error handling.
data Maybe a = Nothing | Just a
  Nothing :: Maybe a
  Just    :: a -> Maybe a
  maybe   :: b -> (a -> b) -> Maybe a -> b

  instance Eq a => Eq (Maybe a)
  instance Ord a => Ord (Maybe a)
  instance Show a => Show (Maybe a)
  instance Read a => Read (Maybe a)
  instance Semigroup a => Semigroup (Maybe a)
  instance Semigroup a => Monoid (Maybe a)

  instance Functor Maybe
  instance Applicative Maybe
  instance Monad Maybe
  instance Foldable Maybe
  instance Traversable Maybe

-- Either an element of one type or an element of another type.
-- Useful for branching and error handling.
data Either a b = Left a | Right b
  Left :: a -> Either a b
  Right :: b -> Either a b
  either :: (a -> c) -> (b -> c) -> Either a b -> c

  instance Semigroup (Either a b)
  instance (Eq a, Eq b) => Eq (Either a b)
  instance (Ord a, Ord b) => Ord (Either a b)
  instance (Show a, Show b) => Show (Either a b)
  instance (Read a, Read b) => Read (Either a b)

  instance Functor (Either a)
  instance Applicative (Either a)
  instance Monad (Either a)
  instance Foldable (Either a)
  instance Traversable (Either a)

-- A type with one element.
data () = ()
  () :: ()

  instance Eq ()
  instance Ord ()
  instance Bounded ()
  instance Enum ()
  instance Show ()
  instance Read ()
  instance Semigroup ()
  instance Monoid ()

----
-- Type aliases
----

-- Lists of characters.
type String = [Char]
  lines   :: String -> [String]
  unlines :: [String] -> String
  words   :: String -> [String]
  unwords :: [String] -> String

-- Strings intended to be used as names of files.
type FilePath = String
  readFile  :: FilePath -> IO String       -- PARTIAL: various failure modes
  writeFile :: FilePath -> String -> IO () -- PARTIAL: various failure modes

-------------
-- Classes --
-------------

----
-- Comparison
----

-- Types whose elements can be compared for equality.
class Eq a
  (/=)   :: Eq a => a -> a -> Bool
  (==)   :: Eq a => a -> a -> Bool
  lookup :: Eq a => a -> [(a, b)] -> Maybe b

-- Totally-ordered types.
class Eq a => Ord a
  (<)  :: Ord a => a -> a -> Bool
  (<=) :: Ord a => a -> a -> Bool
  (>)  :: Ord a => a -> a -> Bool
  (>=) :: Ord a => a -> a -> Bool
  max  :: Ord a => a -> a -> a
  min  :: Ord a => a -> a -> a

-- Bounded types.
class Bounded a
  maxBound :: Bounded a => a
  minBound :: Bounded a => a

-- Enumerable types.
class Enum a
  pred :: Enum a => a -> a -- PARTIAL: fails if out of bounds
  succ :: Enum a => a -> a -- PARTIAL: fails if out of bounds

----
-- Encoding
----

-- Types whose elements can be encoded as strings.
class Show a
  show  :: Show a => a -> String
  print :: Show a => a -> IO ()

-- Types whose elements can be decoded from strings.
class Read a
  read  :: Read a => String -> a -- PARTIAL: fails if no parse
  reads :: Read a => String -> [(a, String)]

----
-- Computation
----

-- A type together with an associative binary operation.
class Semigroup a
  (<>) :: Semigroup a => a -> a -> a

-- A semigroup with an identity element.
class Semigroup a => Monoid a
  mempty  :: Monoid a => a
  mconcat :: Monoid a => [a] -> a

-- Roughly analogous to rings.
class Num a
  (+)         :: Num a => a -> a -> a
  (-)         :: Num a => a -> a -> a
  (*)         :: Num a => a -> a -> a
  negate      :: Num a => a -> a
  abs         :: Num a => a -> a
  signum      :: Num a => a -> a
  fromInteger :: Num a => Integer -> a

-- Roughly analogous to fields.
class Num a => Fractional a
  (/)   :: Fractional a => a -> a -> a -- PARTIAL: fails on divide by zero
  recip :: Fractional a => a -> a      -- PARTIAL: fails on divide by zero

-- Fields on which an exponential function is defined.
class Fractional a => Floating a
  pi   :: Floating a => a
  exp  :: Floating a => a -> a
  log  :: Floating a => a -> a
  sqrt :: Floating a => a -> a
  (**) :: Floating a => a -> a -> a

-- Who knows. Probably poorly-named.
class (Num a, Ord a) => Real a

-- Roughly analogous to euclidean domains.
class (Real a, Enum a) => Integral a
  div       :: Integral a => a -> a -> a      -- PARTIAL: fails on divide by zero
  mod       :: Integral a => a -> a -> a      -- PARTIAL: fails on divide by zero
  divMod    :: Integral a => a -> a -> (a, a) -- PARTIAL: fails on divide by zero
  even      :: Integral a => a -> Bool
  odd       :: Integral a => a -> Bool
  gcd       :: Integral a => a -> a -> a
  lcm       :: Integral a => a -> a -> a
  toInteger :: Integral a => a -> Integer
  (^)       :: (Num a, Integral b) => a -> b -> a

-- Things that can be rounded.
class (Real a, Fractional a) => RealFrac a
  floor    :: (RealFrac a, Integral b) => a -> b
  ceiling  :: (RealFrac a, Integral b) => a -> b
  round    :: (RealFrac a, Integral b) => a -> b
  truncate :: (RealFrac a, Integral b) => a -> b

----
-- Data Structures
----

-- Type constructions where functions on the underlying types can be
-- lifted to functions on the structures.
class Functor f
  fmap :: Functor f => (a -> b) -> f a -> f b

-- Functors admitting a pair of natural transformations
-- (F a, F b) -> F (a, b) and a -> F a.
class Functor f => Applicative f
  pure  :: Applicative f => a -> f a
  (<*>) :: Applicative f => f (a -> b) -> f a -> f b

-- Functors admitting a pair of natural transformations
-- F (F a) -> F a and a -> F a.
class Applicative m => Monad m
  return :: Monad m => a -> m a
  (=<<)  :: Monad m => (a -> m b) -> m a -> m b
  (>>=)  :: Monad m => m a -> (a -> m b) -> m b

-- Type constructions that are somewhat like lists.
class Foldable t
  foldMap   :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
  foldr     :: Foldable t => (a -> b -> b) -> b -> t a -> b
  foldl     :: Foldable t => (b -> a -> b) -> b -> t a -> b
  null      :: Foldable t => t a -> Bool
  length    :: Foldable t => t a -> Int
  elem      :: (Foldable t, Eq a) => a -> t a -> Bool
  notElem   :: (Foldable t, Eq a) => a -> t a -> Bool
  and       :: Foldable t => t Bool -> Bool
  or        :: Foldable t => t Bool -> Bool
  all       :: Foldable t => (a -> Bool) -> t a -> Bool
  any       :: Foldable t => (a -> Bool) -> t a -> Bool
  concat    :: Foldable t => t [a] -> [a]
  concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
  sum       :: (Foldable t, Num a) => t a -> a
  product   :: (Foldable t, Num a) => t a -> a
  maximum   :: (Foldable t, Ord a) => t a -> a
  minimum   :: (Foldable t, Ord a) => t a -> a

-- Type constructions that are both a functor and foldable.
class (Functor t, Foldable t) => Traversable t
  traverse  :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
  sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)