Here are a few useful packages you might want to use when building software with Haskell:
base - Haskell standard library. Contains large collection of useful libraries ranging from data structures to parsing combinators and debugging utilities.
containers - Contains efficient general-purpose implementations of various immutable container types including sets, maps, sequences, trees, and graphs.
The size of each “pixel” should be controlled by a parameter
Your input should be a list of list of colors
If a row is not long enough fill the rest of it with the color white
Bonus: Choose a pallete of 8 or 16 basic colors and read a file containing numbers from 0 to 7 (or 15)
separated by spaces and newlines, and output it’s image
RPN Calculator
Create a program that calculates an arithmetic expression written in reverse polish notation.
Implement the following operations:
literal integers, +, -, *, /, negate
Example execution:
$ rpn-calc 5 7 2 negate + *
25
Lambda Calculus
Overview
The lambda calculus is a minimalistic language that is in the core of functional programming.
It presents a minimalistic framework to learn about many common features in functional languages.
While this section isn’t strictly necessary, and you can skip it, it does provide some
insight about the core of Haskell.
This is a simplified view of how kinds are represented in GHC:
dataKind=Type-- can also be written as: *
| KArrKindKind-- KArr in Haskell this is written as: ->
Think of Type being the kind of concrete (or inhabited) types, and KArr is a function from Kind to Kind.
If a type is parametarized (when defining the ADT you pass it parameters)
then in order for it to be concrete you have to supply it with all the types it expects to get.
Example:
dataBool=True
| FalsedataMaybea=Justa
| Nothing
Bool is not parametarized so it is a concrete type (which means it’s kind is Type)
and has the Values True and False.
Maybe is not a concrete type, it need to be supplied with a type for a. (It has the kind Type -> Type).
Maybe Bool is a concrete type because all of the paramters for Maybe have been supplied.
An expression can only have a type with the kind Type.
Examples:
Value
Type
Kind
Comments
True
Bool
Type (also written *)
a value
‘c’
Char
Type
“Hello”
String
Type
not True
Bool
Type
function application
Just True
Maybe Bool
Type
[“Hello”]
[String]
Type
Nothing
Maybe a
Type
polymorphic
id
a -> a
Type
a function
map
(a -> b) -> [a] -> [b]
Type
map not
[Bool] -> [Bool]
Type
partially applied function
getLine
IO String
Type
putStrLn
String -> IO ()
Type
Void
Type
a concrete types with no values
Maybe
Type -> Type
isn’t fully supplied with parameters
IO
Type -> Type
Either
Type -> Type -> Type
Either a
Type -> Type
partially supplied with parameters
Free
(Type -> Type) -> Type -> Type
the first argument is of higher kind
You can use ghci to query the kind of a type using :kind
Why do we care about Kinds? It let us generalize things and create abstractions.
Let’s take a look at a data type that uses higher kinds:
dataRecfa=Reca (f (Recfa))
This data type has two type parameters, f and a.
From their use in the right side of the = we can see that a has the kind Type because
it is placed as a field without type arguments. We can also see that f has kind Type -> Type
because it is placed as a field with one type argument (which in this case, is the same data type we defined).
This makes Rec kind to be (Type -> Type) -> Type -> Type.
Why is this data type interesting? Let’s try to plug some types and see.
We need some a which as kind Type so let’s just choose Int for now, and let’s use Maybe for f.
Let’s look at some values of our new type Rec Maybe Int.
x1 = Rec 1 Nothing
x2 = Rec 1 (Just (Rec 2 Nothing))
x3 = Rec 1 (Just (Rec 2 (Just (Rec 3 Nothing))))
See a pattern here? it seems like this is an encoding of a non-empty list:
You always have at least one value
Nothing is similar to Nil
Just is similar to Cons
Let’s take a look at another example with this type:
dataIdentitya=Identitya
Identity basically just holds a value of type a. Nothing interesting here.
Let’s try to plug it in Rec (and get Rec Identity Int) and see what kind of value we can have:
Try to plug into our Rec a different type of kind Type -> Type that you know and see what happens!
What is IO?
Overview
It is a parametarized type constructor (it has the kind Type -> Type).
IO a represents a description of a program (or subroutine) that when executed
will produce some value of type a and may do some I/O effects while at it.
Evaluating an IO a is pure - the evaluation will always reduce to the same description of a program.
In an executable, you need to define main :: IO () - a description of a program to run. The Haskell runtime will execute this.
You can combine subroutine descriptions to create bigger subroutine descriptions:
pure :: a -> IO a
Produces a value without doing any I/O.
Example: pure True
Which has the type IO Bool, will not do any I/O and when executed will produce a value of type Bool, specifically True.
fmap :: (a -> b) -> IO a -> IO b
Similar to map on lists, it will apply a function on the parameter of IO.
Example: fmap not (pure True)
Which has the type IO Bool will not do any I/O and when executed will produce a value of type Bool by first applying the function not on the result of pure True,
and so will produce the value False.
(>>) :: IO a -> IO b -> IO b
Run this first thing, discard the result, and then run the second thing.
Example:
putStrLn"Hello">>putStrLn"World"
Which has the type IO (), when executed, will print the string Hello and then will print the string World
and will produce a value of type (), specifically () (in this case the value has the same name as the type).
(>>=) :: IO a -> (a -> IO b) -> IO b
Run this first thing, take its result, pass it to the function which is the second argument, and then execute that.
Example: getLine >>= putStrLn
Which has the type IO () will read a String from the user, apply that String to putStrLn and then execute it,
thus printing the same string it got from the user.
Then it will produce a value of type (), specifically ().
Note: You can implement (>>) using (>>=) like this:
(>>) prog1 prog2 = prog1 >>=\_ -> prog2
join :: IO (IO a) -> IO a
Takes a description of a program that produces a description of a program that produces a value of type a
and converts it to a descrption of a program that will produce a value of type a by executing the first, and then executing the result.
Example: join (fmap putStrLn getLine)
Which is the same as getLine >>= putStrLn.
As you can see we can implement >>= using fmap and join
(>>=) prog func = join (fmap func prog)
There are many more functions and combinators that return IO a. You can view some of them in the module System.IO.
Do notation
do notation is syntactic sugar around >> and >>=.
Example:
main =doputStrLn"Tell me your name."let greet name ="Hello, "++ name ++"!"
name <-getLineputStrLn (greet name)
Will be desugared to:
main =putStrLn"Tell me your name.">>let
greet name ="Hello, "++ name ++"!"ingetLine>>=\name ->putStrLn (greet name)
A regular line that does not create a binding will be sequenced to the next using >>
A new definition can be created using let, it will be translated to let <definition> in <rest of the lines in the do>
A line that creates a binding with <- will use >>= to pass the result and the lambda (\name ->) is used to bind the variable to the result
The last line will remain the same - no desugar needed
This is basically CPS (continuation passing style).
code
operator
type of the left side
type of the right side
comments
let gretting = “hello”
=
String
String
= means both side are interchangeable (they both mean exactly the same thing)
let mygetline = getLine
=
IO String
IO String
Here we just create a new name that is identical to getLine. We are not running anything
name <- getLine
<-
String
IO String
<- is syntactic sugar for >>= where we bind the result of the computation to the name
IO’s API fits a pattern that can be seen in more types in Haskell, which is why the type signatures
of the functions presented here are more general. We’ll discuss that later.
Exercises
Implement a number guessing game
Generate a random number between 1 and 100, the user should try to guess what it is.
If the user guess is too high, say it’s too high.
If the user guess is too low, say it’s too low.
Hint: you can use randomRIO to generate a random number
Bonus: Remember the amount of times the user guesses and print that at the end of the game.
Hint: In pure functional programming we use recursion to emulate state
Bonus: Remember the user’s guesses and tell them if they already tried that guess.
Create an interactive interface that lets the user repeatedly write calculations
and return the evaluations for them
Type classes
Overview
We use type classes to describe groups of types that all behave in a similar way and refer to them generically.
A good type class will have operations on the type and laws attached to it - similar to abstract algebra.
Laws cannot be enforced by the compiler - a good convention in Haskell is not to define lawless type classes and not implement unlawful instances.
We define a type class like this:
classEq (a::*) where(==)::a->a->Bool
We define a class of types that can implement the operation (==).
We implement an instance of a type class for a given type like this:
-- In this case we place `Bool` in place of `a` everywhereinstanceEqBoolwhere(==) b1 b2 =case (b1, b2) of
(True, True) ->True
(False, False) ->True
_ ->False
Now we can implement polymorphic functions that will work on a subset of all types - all types that fill the constraint - have instances of a type class.
(/=)::Eqa=>a->a->Bool(/=) x y =not (x == y)
class instances should be defined in the same place as the type class definition or at the same place as the type definitions.
Failing to do that may cause Orphan Instances.
Abstraction
definition
different substitutions
comments
No polymorphism
func1 :: Int -> Int -> Int
none
we know exactly which types are used and can do all kinds of operations on them
Parametric polymorphism
func2 :: a -> a -> a
a can be any type
We don’t know which type a is and can’t do any type related operations on it
Type classes (ad-hoc)
func3 :: Ord a => a -> a -> a
a can be any type that can be ordered (Bool, Int, String)
anything to the left of => is a constraint on the type
There are quite a few ways to indicate and handle errors in Haskell.
We are going to look at one solution: using the type Either. Either is defined like this:
dataEitherab=Lefta
| Rightb
Simply put, a value of type Either a b can contain either a value of type a, or
请发表评论