Skip to content

Instantly share code, notes, and snippets.

@hanshoglund

hanshoglund/ex.md

Last active September 3, 2018 14:21
Show Gist options
  • Save hanshoglund/23cf49c9c157e449ade1f5ace8fbb8d3 to your computer and use it in GitHub Desktop.
Save hanshoglund/23cf49c9c157e449ade1f5ace8fbb8d3 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ex.md

See also https://en.wikibooks.org/wiki/Haskell

HS excercises

Basics

  • GHC CLI & Repl. Stack. Standard (strict) compiler flags to use.

    1. Create a reproducible shell environment containing the packages network and warp using Stack (LTS, using astack.yaml file) or Nix (HEAD, using ghcWithPackages).
    2. Start a REPL session (using ghci or stack repl) and import Warp in the REPL session.
    3. Write and compile a Hello World program using ghc Hello.hs in the above environment
    4. Import Warp and write a web server printing Hello, World! on localhost:SOMEPORT
    5. Declare a library with a single module module MyLib where myLibText = "Hello library!" using a file mylib.cabal. Build it using cabal build or stack build.
    6. Import the library into your web server application and replace the printed text with the value of myLibText.

  • Misc tooling (non-build systems): hlint, formatters, haddock, hoogle, ghc-mod, ghcid.

  • Basic types: tuples, lists, Either, Bool, Char, WordN, IntN, Integer, Scientific, Rational

    1. Implement toFinite :: Rational -> Maybe Scientific, returning Just x for numbers that has a finite decimal expansion.
    2. What is the difference between Scientific and Double?
    3. What is (minBound, maxBound) for Int8?
    4. When should you use the type Word32? (when you want to represent numbers between 0 and 2^32 with modulo arithmetic).
    5. When should you use the type Int? (answer: rarely - when you want to represent integers close to 0 and performance really matters).
    6. Implement mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c]) in terms of Data.List.foldr

  • Defining ADTs. Pattern matching.

  • Bytestring: strict, lazy, small. Binary I/O and Unicode encoding.

    1. Use qualified imports to import both strict and lazy bytestrings and implement
    concatChunks :: [Strict.ByteString] -> Lazy.ByteString`
    1. What is the difference between ByteString and Builder? (answer: performance of append - compare DList)
    2. When should you use strict, lazy and ShortByteString?

  • String, Text, Unicode. Data.Char.

    1. Write a simple CLI program to convert between UTF8 and UTF16 Little-Endian, using Data.Text.Encoding.
    2. Extend the above program to take a CLI flag for output encoding, detecting input automatically using the Byte Order Mark.

  • Import/Export. Module hierarchy "design" (backpack?).

  • Syntactic sugar. ViewPatterns, Pattern synonyms. LambdaCase. ApplicativeDo. List/Monad comprehensions. OverloadedStrings/Lists etc.

  • Basic strictness. Seq and BangPatterns.

  • System environment/file system. filepath, directory, random, time, process, unix/Win32

    1. Implement a recursive directory list function listDirectoryRecursive :: FilePath -> [FilePath]
    2. Write a program that creates N (e.g. 4096) unique files each containing a different random Int8 followed by a newline (e.g. the ASCII text 421\n).
    3. Write a program that finds the most common number from such a set of files.
    4. Write a program that finds the most recently modified file in a given directory (using file system meta-data).

  • Panic/Error, stack traces

    1. Denotationally/semantically, what is the difference between the following? (answer: none, they all denote bottom)
    a = let x = x in x
b = undefined
c = error "Not defined"
d = head []
    1. In practice, what is the difference between the above? (answer: All except (a) are implemented as GHC exceptions, thought in practice these exceptions are rarely caught. error and undefined give a stack traces in recent GHC)

  • Basic TCs (Eq, Ord, Show, Read, Enum). Stock deriving

    1. Implement
    type DB = State [(String, String)]
put :: Show a => String -> a -> DB ()
get :: Read a => String -> State DB (Maybe a)
    1. What does this print? Why?
    test1 = do
  put "x" 3.5
  put "x" 2
  x <- get "x"
  case x of
    Nothing -> print "nope"
    Just x -> print $ 1 + x
    1. Can we change it to print '3'?
    2. Write an expression using enum syntax [n..] that will fail at runtime.
    3. Define a typeclass Countable a where { minMax :: (Integer, Integer), toI :: a -> Integer, fromI :: Integer -> a } which maps values onto the integers, and uses modulo arithmetic instead of runtime failure. Define instances for Bool, and Int32
    4. Implement instance Countable a => Countable [a]
    5. Implement instance (Countable a, Countable b) => Countable (a -> b)

  • Numeric TCs (Num, Fractional, Real, RealFrac, Floating)

    1. Which typeclasses appear in the type of these expressions: 1, 1.5, 2/3
    2. Which typeclass encodes the predicate "types onto which the integers can be embedded"
    3. Which typeclass encodes the predicate "types which can be embedded onto the integers"
    4. What constraint (set of typeclasses) expresses "isomorphic to the rationals"
    5. What does sqrt 2**2 == 2 evaluate to?
    6. What does (1/0) == (2/0) evaluate to?
    7. Implement the following
    TODO basic conversions, prime fractions etc

  • Defining basic TCs. constraints, instance resolution. MultiParamTypeClasses, fundeps.

  • Typeable. GADTs like (SomeException), wrapping dictionaries. 'constraints'

    1. Using the functions from Data.Typeable to implement
    data Any :: Type
toAny :: Typeable a => a -> Any
fromAny :: Typeable a => Any -> Maybe a
    1. Using the functions in Data.Typeable implement
    data SomeNum :: Type
toSomeNum :: (Typeable a, Num a) => a -> SomeNum
fromSomeNum :: (Typeable a, Num a) => SomeNum -> Maybe a
fromInteger :: Integer -> SomeNum
    1. Can we implement a valid Num instance for SomeNum? If not, why?
    2. Using the functions in Data.Typeable implement
    data SomeList :: Type
instance Semigroup SomeList
instance Monoid SomeList
reverse :: SomeList -> SomeList
length :: SomeList -> Natural
toSomeList :: Typeable a => [a] -> SomeList
fromSomeList :: Typeable a => SomeList -> [a]

  • Newtypes. For renaming (good/bad?), overriding type classes. GeneralizedNewtypeDeriving.

    1. Implement a type for natural numbers based on Integer. Use a newtype and runtime checking with error to preserve the runtime invariant that values x < 1 (or x = ⊥) for any x :: Integer.
    2. Implement newtype wrappers for some standard SI base units and prefixes. E.g. newtype Micro a = Micro a deriving (Eq, Ord, Num, Fractional, Read, Show). Use a type class to provide an overloaded conversion convert such that e.g. trans (Kilo x) == 10^4 * Deci x

  • Collections: Seq, Map, Set. Unordered ditto, performance.

  • IO monad, ST monad. IORef, STRef.

  • Pure monads (Reader, Writer, State, Identity, Const, [], Maybe, Either x).

  • More data structures: trees, graphs, tries, finger trees, priority queues, DLists.

    1. Write a function showTree :: (a -> Char) -> Tree a -> String which draws a tree.
    2. When you should you use DList instead of [] (answer: when you need fast append or snoc)

  • GHC Exceptions. Dynamic throw catch. Exception catching. Async exception marking + Bracket pattern.

  • Pure error handling (ExceptT, UIO, BIO).

  • Phantom types. Proxy, Tagged.

  • DeepSeq. Strict extensions. UNPACK.

  • QuickCheck. Property testing. Typeclass law testing.

  • Semigroup/Monoid. Foldable/Foldable1.

  • Functor/Applicative/Monad. Traversable.

    1. Write two invalid Functor instances for Maybe, invalidating each functor law and provide counter-examples.
    • TODO show via Data.Functor.*, Proxy, Maybe etc what monad/applicative instances are possible
    1. Is ZipList a monad?
    2. Implement mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) in terms of traverse

  • Alternative/MonadPlus. Parsing, logic programming (MonadLogic?). 2. Given

    type Person = Text
class MonadPlus f => MonadRelation f where
  parent :: Person -> f Person
  child :: Person -> f Person

    implement

    descendant :: MonadRelation f => Person -> f Person
sibling :: MonadRelation f => Person -> f Person
firstCousinsOnceRemoved :: MonadRelation f => Person -> f Person

    http://hackage.haskell.org/package/logict-0.6.0.2/docs/Control-Monad-Logic-Class.html

  • Functor family ('normal' encoding): Contravariant, Profunctor, Bifunctor, Biapplicative

    1. Which of the following types are instances Functor (covariant), Contravariant, or both?
    • data Identity a = Identity a (answer: covariant)
    • data Equiv a = Equiv (a -> a -> Bool) (answer: contravariant)
    • data Sink a = Sink (a -> IO ()) (answer: contravariant)
    • data Sender = Sender (Sink a -> IO ()) (answer: covariant)
    • data Proxy a = Proxy (answer: both)
    • Constant () :+: Identity (answer: covariant)
    • Equiv :.: Equiv (answer: covariant)
    • Proxy :.: Identity (answer: both)

  • Deriving and using serialization classes (JSON, binary/cereal). Problems with schema-free serialization.

Intermediate

  • GHC Concurrency I: Threads/MVars

    1. Write a program that forks N threads, each of which blocks for a random amount of time (using threadDelay). Make the program print the ThreadId of the last thread to unblock.

  • GHC Concurrency II: STM, async

    1. Write a web server that waits for two concurrent requests A and B, then serves the request body of A as the response to B and vice versa.
    2. Write a CLI on top of the above HTTP API (e.g. using http-client) supporting the following interaction
    ./app
> Please enter your name
Amor
> Waiting for partner...
> Your partner is Psyche.

  • GHC Concurrency III: More bracket. Async exceptions. Masking. Interruptible.

  • Compile with profiling/optimizations. ThreadScope, EKG.

  • RankNTypes. forall, existentials. Free theorems. ScopedTypeVariables. TypeApplication.

  • Type class implementations. Default signatures. MINIMAL pragma. Derive strategies (newtype/via and stock eclipse them all!)

  • Kind system. Higher-kinded types. ConstraintKinds, promotion.

  • TFs and associated types (basics, injectivity, relation to fundeps)

  • More GeneralizedNewtypeDeriving. Roles system.

  • Free monads

      1. Define Tree (from containers:Data.Tree) in terms of Free (from free)

  • Monad transformers. How natural transformations often generalize free/transformers.

  • Data types a la carte. Writing isomorphisms between data types.

  • GHC generics.

  • Alt-generics. SOP.

  • Lazy IO problems (sticking to readFile/streaming libraries). The IO manager (based on underlying async IO APIs).

  • Pipes/conduits (a.k.a. collaborative multitasking via transformers)

  • Basic lenses (not van Laarhoven)

    data Lens s a  = Lens  { get :: s -> a, set :: s -> a -> s }
data Prism s a = Prism { view :: s -> Maybe a, set :: s -> a -> s }
    1. Write Category instances for Lens and Prism
    2. Write a lens _1 to the first element of a tuple (using a type class).
    3. Write a prism _Left to the first element of an Either.

  • Van Laarhoven lenses & related optics (lens, prism, iso, fold, traversal).

  • State machines: folds/foldl/machines.

  • Arrows and 'Kleisli'. Relation to state machines (arrowized FRP).

  • Classical FRP. Event/Behavior. reactive-banana. Implementing it.

  • Finally tagless effects

  • F-algebras, Fix, Recursion schemes.

  • Pretty-printing libraries.

  • Shake

  • Parsing libraries (base, parsers, optparse-applicative, parsec, attoparsec, trifecta)

  • Other free structures: Applicative, Alternative, Monoid, Group etc.

  • Comonads. Free Comonads. Kan extensions. Coyoneda.

  • Alternative (non Cabal/Stack) build systems. Nix.

  • GC. Stack vs. heap. Finalizers.

  • GADTs and contraints. Free APIs. Leibniz equality.

  • Indexed monads.

  • RPC: StaticPointers. Singletons for Strongly typed channels.

  • HTTP, HTTPS, Websockets. WAI/warp stack. Servant.

  • SQL/database libraries

  • Badness of Haskell records. RowType alternatives? vinyl.

  • Unsafe functions. Partiality, unsafePerformIO. Safe Haskell.

Advanced

Misc

  • The C FFI. c2hs
  • TemplateHaskell, CPP, code generation.
  • GHC vs standards. Other implementations. Core libraries (https://wiki.haskell.org/Library_submissions).
  • Cabal pacakge constraints. Curated package sets (Haskell platform, Stackage, Nix).
  • GUI (gloss, threepenny, TODO)
  • Plugins. GHC API. 'hint' package.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment