# CIS 194: Introduction to Haskell ## Metadata **Created**:: [[2026-01-26]] **Host**:: [seas.upenn.edu](http://www.seas.upenn.edu) **Source**:: #from/clipper **Status**:: #x **Title**:: Lecture notes and assignments **URL**:: [www.seas.upenn.edu](https://www.seas.upenn.edu/~cis1940/spring13/lectures.html) **Zettel**:: #zettel/fleeting **Topic**:: [[♯ Programming]] **Parent**:: [[Haskell]] ## Tasks ### Week 1 - [x] Study: [Introduction to Haskell](https://www.seas.upenn.edu/~cis1940/spring13/lectures/01-intro.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/01-intro.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/01-intro.lhs)) - [x] *Learn You a Haskell for Great Good!* [Chapter 2. Starting Out](https://learnyouahaskell.github.io/starting-out.html) - [x] *Real World Haskell* [Chapter 1. Getting started](https://book.realworldhaskell.org/read/getting-started.html) - [x] *Real World Haskell* [Chapter 2. Types and functions](https://book.realworldhaskell.org/read/types-and-functions.html) - [x] Complete: [Homework 1](https://www.seas.upenn.edu/~cis1940/spring13/hw/01-intro.pdf) #### Notes - Function as operator: ```haskell mod 19 3 19 `mod` 3 ``` - Negative numbers must often be surrounded by parentheses #caveat - For integer division we can use `div`. - Negation: `not`, `/=` - [[Haskell Pattern Matching]] - Note that function application has higher precedence than any infix operators. - `[1..3]` is `[1,2,3]` - `1,2` in Rust - List with step indicated by first two elements: `[3,6..20]`, `[20,19..1]` - Infinite list: `take 24 [13,26..]` - List comprehensions: `[ x | x <- [10..20], x /= 13, x /= 15, x /= 19]` - List comprehensions can have definitions `let best = ...` - ghci - We can use ghci to inspect the precedence levels of individual operators, using its `:info` command. - `:set +t` prints expression type info, or one pass `:type` - `:load add.hs` ### Week 2 - [x] Study: [Algebraic Data Types](https://www.seas.upenn.edu/~cis1940/spring13/lectures/02-ADTs.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/02-ADTs.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/02-ADTs.lhs)) - [x] *Real World Haskell* [Chapter 3. Defining Types, Streamlining Functions](https://book.realworldhaskell.org/read/defining-types-streamlining-functions.html) - [x] Complete: [Homework 2](https://www.seas.upenn.edu/~cis1940/spring13/hw/02-ADTs.pdf) - Resources: [error.log](https://www.seas.upenn.edu/~cis1940/spring13/extras/02-ADTs/error.log), [sample.log](https://www.seas.upenn.edu/~cis1940/spring13/extras/02-ADTs/sample.log), [Log.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/02-ADTs/Log.hs) #### Notes - Data type and value constructor can have the same name. - Record syntax ```haskell -- delclaration { accessor :: Type, ... } -- initialization { accessor = value, ... } ``` - It's common to add prefix to value constructor and accessor functions. - Panic: `error :: String -> a` - Use spaces for indentation - Named pattern `x@pat` ### Week 3 - [x] Study: [Recursion patterns, polymorphism, and the Prelude](https://www.seas.upenn.edu/~cis1940/spring13/lectures/03-rec-poly.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/03-rec-poly.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/03-rec-poly.lhs)) - [x] Complete: [Homework 3](https://www.seas.upenn.edu/~cis1940/spring13/hw/03-rec-poly.pdf) #### Notes - [Safe](https://hackage.haskell.org/package/safe) alternatives for partial functions in Prelude. ### Week 4 - [x] Study: [Higher-order programming and type inference](https://www.seas.upenn.edu/~cis1940/spring13/lectures/04-higher-order.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/04-higher-order.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/04-higher-order.lhs)) - [x] *Learn You a Haskell for Great Good!* [Chapter 6. Higher Order Functions](https://learnyouahaskell.github.io/higher-order-functions.html) - [x] Complete: [Homework 4](https://www.seas.upenn.edu/~cis1940/spring13/hw/04-higher-order.pdf) #### Notes - `(-5)` is not a partial applied function, use `subtract`. - Use `foldl'` by default for most operations; use `foldl` only if you need lazy evaluation. - `{-# LANGUAGE BangPatterns #-}` and `!x` to force expanding variable `x`. - Use `seq` to expand the first then return the second - `$!` is an alternative of ` but expanding the second parameter - Weak Head Normal Form: "minimum amount of evaluation needed" to see the structure of an expression. ### Week 5 - [x] Study: [More polymorphism and type classes](https://www.seas.upenn.edu/~cis1940/spring13/lectures/05-type-classes.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/05-type-classes.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/05-type-classes.lhs)) - [x] Complete: [Homework 5](https://www.seas.upenn.edu/~cis1940/spring13/hw/05-type-classes.pdf) - Resources: [ExprT.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/05-type-classes/ExprT.hs), [Parser.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/05-type-classes/Parser.hs), [StackVM.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/05-type-classes/StackVM.hs) #### Notes - Parametric polymorphism - Type-class polymorphism - `class Eq a where` - `instance Eq Foo where` - Type annotation for multiple terms: `(==), (/=) :: a -> a -> Bool` - [[Haskell Applicative]] - [[Haskell High-Order Function Composition]] ### Week 6 - [x] Study: [Lazy evaluation](https://www.seas.upenn.edu/~cis1940/spring13/lectures/06-laziness.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/06-laziness.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/06-laziness.lhs)) - [x] Complete: [Homework 6](https://www.seas.upenn.edu/~cis1940/spring13/hw/06-laziness.pdf) #### Notes - Interesting Fibonacci implementations in the homework. ### Week 7 - [x] Study: [Folds and monoids](https://www.seas.upenn.edu/~cis1940/spring13/lectures/07-folds-monoids.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/07-folds-monoids.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/07-folds-monoids.lhs)) - [x] Learn You a Haskell, [Only folds and horses](https://learnyouahaskell.github.io/higher-order-functions.html#folds) - [x] Learn You a Haskell, [Monoids](https://learnyouahaskell.github.io/functors-applicative-functors-and-monoids.html#monoids) - [x] [Fold](http://haskell.org/haskellwiki/Fold) from the Haskell wiki - [x] Heinrich Apfelmus, [Monoids and Finger Trees](http://apfelmus.nfshost.com/articles/monoid-fingertree.html) - [x] Dan Piponi, [Haskell Monoids and their Uses](http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html) - [x] [Data.Monoid](https://hackage.haskell.org/package/base-4.22.0.0/docs/Data-Monoid.html) documentation - [x] [Data.Foldable](https://hackage.haskell.org/package/base-4.22.0.0/docs/Data-Foldable.html) documentation - [x] Complete: [Homework 7](https://www.seas.upenn.edu/~cis1940/spring13/hw/07-folds-monoids.pdf) - Resources: [Editor.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/07-folds-monoids/Editor.hs), [Buffer.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/07-folds-monoids/Buffer.hs), [Sized.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/07-folds-monoids/Sized.hs), [StringBuffer.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/07-folds-monoids/StringBuffer.hs), [StringBufEditor.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/07-folds-monoids/StringBufEditor.hs), [carol.txt](https://www.seas.upenn.edu/~cis1940/spring13/extras/07-folds-monoids/carol.txt) #### Notes - `scanl` and `scanr` are like `foldl` and `foldr`, only they report all the intermediate accumulator states in the form of a list. - `:k` is `:t` for types - `[]` and `(->)` are type constructors. The sequence of `(->)` determines that `fmap` applies a function to the returned value. - Use `newtype` to flip type parameters. - Monoid is Semigroup with an identity like (**Related**:: [[Monoid (Math)]]) - Think Monoids as a way to combine things in order and there's a safe default value (identity) to start with. - It's important because "combining with identity" ensures a reliable implementation of `fold`. - Associativity also makes binary search possible. - Default Monoid for Maybe combines inner Monoids when both are `Just`. Use `Alt Maybe` to return the first `Just`. Also see `<|>` in `Control.Alternative`. - `Last a` is equivalent to `Dual (Alt Maybe a)` - `(#.)` is a performance tuning tool to avoid overhead of wrapping/unwrapping newtypes. `MyT #. x` becomes `x`. - `Endo` is a Monoid for function composition on `a -> a`. The corresponding getter is `appEndo`. It is like repeating transformers. - `Foldable.foldMap` turns a wrapped value into `Endo (a->a)` then apply them repeatably on the initial value to get the result. ```haskell foldr (+) 0 [1,2,3] -- [(1+),(2+),(3+)] -- Endo Monoid `mappend` -- (1+) . (2+) . (3+) $ 0 ``` ### Week 8 - [x] Study: [IO](https://www.seas.upenn.edu/~cis1940/spring13/lectures/08-IO.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/08-IO.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/08-IO.lhs)) - [x] LYAH [Chapter 9: Input and Output](https://learnyouahaskell.github.io/input-and-output.html) - [x] RWH [Chapter 7: I/O](https://book.realworldhaskell.org/read/io.html) - [x] Complete: [Homework 8](https://www.seas.upenn.edu/~cis1940/spring13/hw/08-IO.pdf) - Resources: [Employee.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/08-IO/Employee.hs), [company.txt](https://www.seas.upenn.edu/~cis1940/spring13/extras/08-IO/company.txt) #### Notes - Compare Haskell IO and rust async: - `IO` vs `Future` - `do` vs `async` - `<-` vs `await` - `do` block can have `let` without `in` like in list comprehension. - The last IO action in the `do` block cannot be bound to a variable. - `do` is optional if there's only one IO action. - `let ... in` creates a code block can be read from top to down, and the result of each step is assigned to a meaningful name. - safe `read`: `readMaybe` `readEither` - List safe alternatives - `Data.Maybe.listToMaybe` - `uncons`, `unsnoc`, and `NonEmpty` from`Data.List` - Latest version of GHC does not require parenthesis around IO lambda ```haskell import Control.Monad main = do forM_ [1, 2, 3] $ \x -> do print x putStrLn "done" ``` ### Week 9 - [x] Study: [Functors](https://www.seas.upenn.edu/~cis1940/spring13/lectures/09-functors.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/09-functors.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/09-functors.lhs)) - [x] Learn You a Haskell, [The Functor typeclass]() - [x] [The Typeclassopedia](http://www.haskell.org/haskellwiki/Typeclassopedia) - No homework this week #### Notes - `fmap` on `(->) r` is the composition operator `(.)` - Another perspective on `fmap` is that it turns a function to a new function working on wrapper types. - `((.) . (.))` pattern: [[Haskell N-Ary Composition]] ### Week 10 - [x] Study: [Applicative functors (part 1)](https://www.seas.upenn.edu/~cis1940/spring13/lectures/10-applicative.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/10-applicative.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/10-applicative.lhs)) - [x] Complete: [Homework 10](https://www.seas.upenn.edu/~cis1940/spring13/hw/10-applicative.pdf) - Resources: [AParser.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/10-applicative/AParser.hs) ### Week 11 - [x] Study: [Applicative functors (part 2)](https://www.seas.upenn.edu/~cis1940/spring13/lectures/11-applicative2.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/11-applicative2.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/11-applicative2.lhs)) - [x] Complete: [Homework 11](https://www.seas.upenn.edu/~cis1940/spring13/hw/11-applicative2.pdf) - Resources: [AParser.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/11-applicative2/AParser.hs), [SExpr.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/11-applicative2/SExpr.hs) ### Week 12 - [x] Study: [Monads](https://www.seas.upenn.edu/~cis1940/spring13/lectures/12-monads.html) ([html](https://www.seas.upenn.edu/~cis1940/spring13/lectures/12-monads.html), [lhs](https://www.seas.upenn.edu/~cis1940/spring13/lectures/12-monads.lhs)) - [x] Complete: [Homework 12](https://www.seas.upenn.edu/~cis1940/spring13/hw/12-monads.pdf) - Resources: [Risk.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/12-monads/Risk.hs) #### Notes - `<=<` is composition `.` for lifted monad function. ## TICHN - [x] Class and instance - [x] Type constraints, such as a type that supports operator `<`. ``` max :: (Ord a) ``` - [x] Semigroup - [x] Endo: wrapper of `a -> a` to be used as monoid where `mappend` is function composition. It can be used to implement folding. First map each element to a function for `acc -> acc`, then use `mconcat` to compose them together, last call it on the init value. - [x] [Parser.hs](https://www.seas.upenn.edu/~cis1940/spring13/extras/05-type-classes/Parser.hs) - [x] [Parsec](https://hackage.haskell.org/package/parsec) - [x] `Control.Exception` - `finally` - [x] Logging - [x] [Desugaring of do blocks](https://book.realworldhaskell.org/read/monads.html#monads.do) - `(>>)` and `(>>=)` in `Monad` - [x] Documentation: [[Haddock Authors - Documentation and Markup (Highlights)]] - [x] [transformers](https://hackage.haskell.org/package/transformers) - Monads: Reader, Writer, State, Cont ## Resources - [Real World Haskell](https://book.realworldhaskell.org/read/) - [Learn You a Haskell for Great Good!](https://learnyouahaskell.github.io/chapters.html) ## Highlights ### CIS 194 - [[Brent Yorgey - CIS 194 Haskell Basics (Highlights)]] - [[Brent Yorgey - CIS 194 Recursion patterns, polymorphism, and the Prelude (Highlights)]] - [[Brent Yorgey - CIS 194 Higher-order programming and type inference (Highlights)]] - [[Brent Yorgey - CIS 194 More polymorphism and type classes (Highlights)]] - [[Brent Yorgey - CIS 194 Lazy evaluation (Highlights)]] ### Learn You a Haskell for Great Good - [[Miran Lipovača - Learn You a Haskell for Great Good Chapter 2. Starting Out (Highlights)]] - [[Miran Lipovača - Learn You a Haskell for Great Good Chapter 6. Higher Order Functions (Highlights)]] - [[Miran Lipovača - Learn You a Haskell for Great Good Chapter 8. Making Our Own Types and Typeclasses (Highlights)]] - [[Miran Lipovača - Learn You a Haskell for Great Good Chapter 11. Functors, Applicative Functors and Monoids (Highlights)]] ### Real World Haskell - [[Bryan O'Sullivan et al. - Real World Haskell Chapter 2. Types and Functions (Highlights)]] - [[Bryan O'Sullivan et al. - Real World Haskell Chapter 3. Defining Types, Streamlining FunctionsM (Highlights)]] ### Others - [[Haskell Authors - Foldl (Highlights)]]