Cheat Sheet
https://jutge.org/doc/haskellcheatsheet.pdf https://wiki.haskell.org/H99:_NinetyNine_Haskell_Problems
Syntax
basic
f :: Int > Int
 definition of f here
f x = x ^ 2 + 2 * x + 4
g :: Int > (Int > Int)
g x y = x * y
types
We have already seen a few of Haskell's builtin basic types:

Int,

Integer, and

Bool. There are many more which you might expect, including:

Char,

String,

Float, and

Double. You may have noticed that all these types begin with a capital letter. This is actually a general rule, with only a small number of exceptions.

list: [Int]

tuple: (Int,Char) is the type 'pairs of one integer and one character'. a list lets you store any number of values of one type a tuple lets you store a fixed number of values of different (but fixed) types
type equivals
type Pair = (Int,Int)
 String is a type synonym for [Char]
e.g.
type Message = ([Char], Int)
valid :: Message > Bool
valid (msg, mID) = correctLength && noSpaces && validID
where
correctLength = (length msg <= 140)
noSpaces = not (elem ' ' msg)
validID = mID >= 1000 && mID <= 9999
type variables
qsort :: Ord a => [a] > [a]
qsort [] = []
qsort (pivot:others) = (qsort lowers) ++ [pivot] ++ (qsort highers)
where lowers = filter (<pivot) others
highers = filter (>=pivot) others
guard
fact :: Integer > Integer
fact n
 n < 0 = 0
 n == 0 = 1
 otherwise = n * fact (n1)
let in
在一个表达式里赋值，类似于where
. 在let 分句定义变量，最后结果以in后的表达式为准。
pack (x:xs) = let (first,rest) = span (==x) xs
in (x:first) : pack rest
pack [] = []
operators
lists
 range [1,2..6] gives [1,2,3,4,5,6]
 brutal range
range_list :: Int > Int > [Int]
range_list min max
 min > max = []
 otherwise = min : range_list (min+1) max
 recursive list
sum :: [Int] > Int
sum [] = 0
sum (x:xs) = x + sum xs
data
data MyBool = MyTrue  MyFalse
mynot :: MyBool > MyBool
mynot MyTrue = MyFalse
mynot MyFalse = MyTrue
data Point = Pt Float Float
 invert: reflect a point (x,y) in the line x = y
invert :: Point > Point
invert (Pt x y) = Pt y x
data Font_Color
= Name String  Hex Int  RGB Int Int Int
data Font_Attribute = Font_Size Int  Font_Face String  Font_Color Font_Color
data Font_tag = [Font_Attribute]
recursive data type
data List a = ListNode a (List a)  ListEnd
 define your function here
 don't forget the type signature!
mymaximum :: Ord a => List a > a
mymaximum (ListNode a ListEnd) = a
mymaximum (ListNode x xs)
 (mymaximum xs) > x = mymaximum xs
 otherwise = x
 derive
data MyBool = MyTrue  MyFalse
deriving (Eq, Show)
data List a = ListNode a (List a)  ListEnd
deriving (Eq, Show)
show
converts from values to string representations, and is used when ghci prints out the result of a function call for you
Maybe
maybeApply :: (a > b) > Maybe a > Maybe b
maybeApply f Nothing = Nothing
maybeApply f (Just x) = Just (f x)
working:
maybeApply (+1) (Just 41)
maybeApply (+1) Nothing
To remove the Just from the head of a string result, use IO:
data ChessPiece = ChessPiece PieceColour PieceRank
toPieceColour :: Char > Maybe PieceColour
toPieceColour 'B' = Just Black
toPieceColour 'W' = Just White
toPieceColour _ = Nothing
toPieceRank :: Char > Maybe PieceRank
toPieceRank 'K' = Just King
toPieceRank 'Q' = Just Queen
toPieceRank 'R' = Just Rook
toPieceRank 'B' = Just Bishop
toPieceRank 'N' = Just Knight
toPieceRank 'P' = Just Pawn
toPieceRank _ = Nothing
 不报错
 toChessPiece :: String > Maybe ChessPiece
 toChessPiece str =
 case filter (/=' ') str of
 [c,r] > do
 colour < toPieceColour c
 rank < toPieceRank r
 return $ ChessPiece colour rank
 _ > Nothing
 报错 expected type ‘PieceColour’ with actual type ‘Maybe PieceColour’
toChessPiece str =
case filter (/=' ') str of
[c,r] >
ChessPiece (toPieceColour c) (toPieceRank r)
_ > Nothing
Alpha expression
linearEqn :: Num a => a > a > [a] > [a]
linearEqn m n list = map (\x > m*x + n) list
simulate while loop
int mccarthy_91(int n)
{
int c = 1;
while (c != 0) {
if (n > 100) {
n = n  10;
c;
} else {
n = n + 11;
c++;
}
}
return n;
}
 The main challenge is the while loop. For the sake of illustration we
 will solve a more general problem. Consider the following generic while
 loop in C which updates variable x in each iteration:
 while (cond(x))
 x = next_version_of(x);
 x = final_version_of(x);
 It can be translated into Haskell as follows
mywhile x =
if cond x then mywhile (next_version_of x)
else final_version_of x
 In the C code there are two variables, so we can make x a pair and use
 the follo wing definitions of cond, next_version_of and final_version_of:
cond (c,n) = c /= 0
next_version_of (c,n) =
if n > 100 then (c1, n10) else (c+1, n+11)
 We simply have to call mywhile with the initial versions of c and n:
final_version_of (c,n) = n
mccarthy_91 :: Int > Int
mccarthy_91 n = mywhile (1, n)
IO
out
putStr :: String > IO ()
putStrLn :: String > IO ()
print :: Show a => a > IO ()
return :: a > IO a
in
getChar :: IO Char
getLine :: IO String
File IO
main
= readFile "inp" >>= \s >
writeFile "outp" (filter isAscii s) >>
putStr "Filtering successful\n"
Do Notation
import Data.Char(isAscii)
main
= do
putStr "Input file: "
ifile < getLine
putStr "Output file: "
ofile < getLine
s < readFile ifile
writeFile ofile (filter isAscii s)
putStrLn "All done"
To ignore indentation:
import Data.Char(isAscii)
main
= do
{ putStr "Input file: "
; ifile < getLine
; putStr "Output file: "
; ofile < getLine
; s < readFile ifile
; writeFile ofile (filter isAscii s)
; putStrLn "All done"
}
other example
module Main where
import Data.Char
import System.Random
 'main' selects a word to be guessed, then enters a dialogue with the
 user to help them determine the secret word:
main :: IO ()
main
= do
dict < readFile "words.txt"  get contents of file "words.txt"
let words = lines dict  separate it into lines (here: words)
let len = length words  count how many words we have
play words len  now play the game
 The function 'play' allows the user to play again and again:
play :: [String] > Int > IO ()
play words n
= do
putStr "Want a challenge (y/n)? "
answer < getLine
if (head answer) == 'y'
then
do
putStrLn "Okay, here it is:"
ran < getStdRandom (randomR (0,n1))  random number in range
let w = words!!ran  w is the secret word;
solve w []  [] initial list of guesses
play words n
else
do
putStrLn "Okay, bye"
return ()
 The interactive solver loop:
solve :: String > String > IO ()
solve word guesses
= do
let indic = indicator word guesses
putStr (" " ++ indic)
if (all isAlpha indic)
then putStrLn (" " ++ show (length guesses) ++ " guesses")
else do
putStrLn ""
guess < response
solve word (guess:guesses)
indicator :: String > String > String
indicator w gs
= [if c `elem` gs then c else ''  c < w]
 Handling the user's input may also require a loop (if input is invalid):
response :: IO Char
response
= do
putStr "guess> "
gs < getLine
if length gs == 1 && isAlpha (head gs)
then return (toLower (head gs))
else do
putStrLn "Just a single letter!"
response
>> and >>=
main
= readFile "inp" >>= \s >
writeFile "outp" (filter isAscii s) >>
putStr "Filtering successful\n"
Note: Do notation is grammar sugar for >> and >>=.
Random
Extract a given number of randomly selected elements from a list.
λ> rnd_select "abcdefgh" 3 >>= putStrLn
eda
rnd_select xs n = do
gen < getStdGen
return $ take n [ xs !! x  x < randomRs (0, (length xs)  1) gen]
show
module ChessPiece (ChessPiece, toChessPiece) where
data ChessPiece = ChessPiece PieceColour PieceRank
data PieceColour = Black  White
data PieceRank = King  Queen  Rook  Bishop  Knight  Pawn
instance Show ChessPiece where
show (ChessPiece c r) = show c ++ show r
instance Show PieceColour where
show Black = "B"
show White = "W"
instance Show PieceRank where
show King = "K"
show Queen = "Q"
show Rook = "R"
show Bishop = "B"
show Knight = "N"
show Pawn = "P"
toChessPiece :: String > Maybe ChessPiece
toChessPiece str =
case filter (/=' ') str of
[c,r] > do
colour < toPieceColour c
rank < toPieceRank r
return $ ChessPiece colour rank
_ > Nothing
toPieceColour :: Char > Maybe PieceColour
toPieceColour 'B' = Just Black
toPieceColour 'W' = Just White
toPieceColour _ = Nothing
toPieceRank :: Char > Maybe PieceRank
toPieceRank 'K' = Just King
toPieceRank 'Q' = Just Queen
toPieceRank 'R' = Just Rook
toPieceRank 'B' = Just Bishop
toPieceRank 'N' = Just Knight
toPieceRank 'P' = Just Pawn
toPieceRank _ = Nothing
Data structure
list
see previous.
Generators
 [x^2  x < [1..6]]
 [(x)  x < [1..6]]
 [even x  x < [1..6]]
[ x^2  x < [1..6] ]
'' ''
expression generator
mymap:
myMap :: (a > b) > [a] > [b]
 define your function here!
myMap f xs = [f x x < xs]
Filters
 [x^2  x < [1..12], even x]
[ x^2  x < [1..12], even x ]
'' '' ''
expression generator filter
应用:
checkPair :: Char > Char > Bool
checkPair x y
 (x == 'A' && y == 'T')  (x == 'T' && y == 'A') = True
 (x == 'C' && y == 'G')  (x == 'G' && y == 'C') = True
 otherwise = False
compDNA :: String > String > Bool
compDNA str1 str2 = (==) (length str1) (length [x  (x,y) < zip str1 str2, checkPair x y])
 Nesting filters
l = [ x++" "++y
 x < ["hello", "fly away", "come back"]
, length x > 7
, y < ["peter", "matthew", "paul"]
, length y < 7
]
结果:
["fly away peter","fly away paul","come back peter","come back paul"]
是嵌套循环, 如果并行同时遍历需要用到zip. zip函数在之后介绍.
set
import Set
same_letters :: String > String > Bool
same_letters word1 word2 = (set word1) == (set word2)
 copy this function into the appropriate place
 inside Set.hs
set_intersect :: Ord a => Set a > Set a > Set a
set_intersect (Set es) b
= set (filter (`set_elem` b) es)
tree
data Tree a = Node a (Tree a) (Tree a)  Empty
size of tree
how many nodes
data Tree a = Node a (Tree a) (Tree a)  Empty
size :: Tree a > Int
size Empty = 0
size (Node x l r) = 1 + size l + size r
height of tree
height which takes a binary tree and calculates its height: the number of nodes in the longest path from root to leaf.
data Tree a = Node a (Tree a) (Tree a)  Empty
 define your function here
 don't forget the type signature!
height :: Tree a > Int
height Empty = 0
height (Node x l r) = 1 + (max (height l) (height r))
inorder traverse into a list
data Tree a = Node a (Tree a) (Tree a)  Empty
 define your function here
 don't forget the type signature!
elements :: Tree a > [a]
elements Empty = []
elements (Node x l r) = (elements l) ++ [x] ++ (elements r)
Binary search
be kept in the usual binary search tree order
data Tree a = Node a (Tree a) (Tree a)  Empty
search :: Ord a => a > Tree a > Bool
search x Empty = False
search x (Node y l r)
 x == y = True
 x < y = search x l
 x > y = search x r
Binary insert
data Tree a = Node a (Tree a) (Tree a)  Empty
deriving Show
 define your function here
 don't forget the type signature!
insert :: Ord a => a > Tree a > Tree a
insert y Empty = (Node y Empty Empty)
insert y (Node x l r)
 y == x = (Node x l r)
 y < x = (Node x (insert y l) r)
 otherwise = (Node x l (insert y r))
Binary build tree
e.g.
Main> buildtree [4,2,6]
Node 6 (Node 2 Empty (Node 4 Empty Empty)) Empty
data Tree a = Node a (Tree a) (Tree a)  Empty
deriving Show
 copy over your solution to the previous exercise,
 so that you have access to the 'insert' function
insert :: Ord a => a > Tree a > Tree a
insert y Empty = (Node y Empty Empty)
insert y (Node x l r)
 y == x = (Node x l r)
 y < x = (Node x (insert y l) r)
 otherwise = (Node x l (insert y r))
 define your function here
 don't forget the type signature!
buildtree :: Ord a => [a] > Tree a
buildtree [] = Empty
buildtree (x:xs) = insert x (buildtree xs)
Construct Binary tree
data Tree a = Empty  Branch a (Tree a) (Tree a) deriving (Show, Eq)
leaf x = Branch x Empty Empty
main = putStrLn $ concatMap (\t > show t ++ "\n") balTrees
where balTrees = filter isBalancedTree (makeTrees 'x' 4)
isBalancedTree :: Tree a > Bool
isBalancedTree Empty = True
isBalancedTree (Branch _ l r) = abs (countBranches l  countBranches r) <= 1
&& isBalancedTree l && isBalancedTree r
isBalancedTree _ = False
countBranches :: Tree a > Int
countBranches Empty = 0
countBranches (Branch _ l r) = 1 + countBranches l + countBranches r
 makes all possible trees filled with the given number of nodes
 and fill them with the given value
makeTrees :: a > Int > [Tree a]
makeTrees _ 0 = []
makeTrees c 1 = [leaf c]
makeTrees c n = lonly ++ ronly ++ landr
where lonly = [Branch c t Empty  t < smallerTree]
ronly = [Branch c Empty t  t < smallerTree]
landr = concat [[Branch c l r  l < fst lrtrees, r < snd lrtrees]  lrtrees < treeMinusTwo]
smallerTree = makeTrees c (n1)
treeMinusTwo = [(makeTrees c num, makeTrees c (n1num))  num < [0..n2]]
Expression Tree
e.g.
(x)
/ \
() (+)
/ \ / \
(x) (3) (1) (1)
/ \
(4) (6)
data Expr
= Number Int
 Plus Expr Expr
 Minus Expr Expr
 Times Expr Expr
 Divide Expr Expr
evaluate
data Expr
= Number Int
 Plus Expr Expr
 Minus Expr Expr
 Times Expr Expr
 Divide Expr Expr
 define your function here
 don't forget the type signature!
evaluate :: Expr > Int
evaluate (Number x) = x
evaluate (Plus x y) = evaluate x + evaluate y
evaluate (Minus x y) = evaluate x  evaluate y
evaluate (Times x y) = evaluate x * evaluate y
evaluate (Divide x y) = div (evaluate x) (evaluate y)
Functions
fib
fib :: Int > Int
 define fib function here
fib 0 = 0
fib 1 = 1
fib x = fib (x  1) + fib (x  2)
fact
fact :: Integer > Integer
fact n
 n < 0 = 0
 n == 0 = 1
 otherwise = n * fact (n1)
leap year
leap :: Int > Bool
leap year
 year `mod` 4 /= 0 = False
 year `mod` 100 /= 0 = True
 year `mod` 400 /= 0 = False
 otherwise = True
xor
 'xor' is really just the same as
 'not equals' for Booleans:
xor :: Bool > Bool > Bool
xor x y = x /= y
 That was too easy!
 Here are some alternative solutions:
 By enumerating all patterns:
xor' False False = False
xor' False True = True
xor' True False = True
xor' True True = False
head
builtin
 Define your myHead and myTail functions here
myHead [] = error "no head for null"
myHead (x:_) = x
myTail [] = error "no tail for null"
myTail (_:xs) = xs
last
last [x] = x
last (x:xs) = last xs
append
append [] lst = lst
append (e:es) lst = e : append es lst
reverse
 Define your myReverse function here
append [] lst = lst
append (e:es) lst = e:append es lst
myReverse [] = []
myReverse (x:xs) = append (myReverse xs) [x]
getNthElem
Implement a function getNthElem which takes an integer n and a list, and returns the nth element of the list.
getNthElem n [] = error "n was too big in getn"
getNthElem n (x:xs)
 n > 1 = getNthElem (n1) xs
 n == 1 = x
 otherwise = error "n was too small in getn"
isEven
isEven 0 = True
isEven 1 = False
isEven (n + 2) = isEven n
 or
evn :: Int > Bool
evn x = (x `mod` 2 == 0)
maximum
maximum :: [Int] > Int
maximum [x] = x
maximum (x:xs)
 x > maxxs = x
 otherwise = maxxs
where maxxs = maximum xs
search
search :: Int > [Int] > Bool
search x [] = False
search x (y:ys)
 x == y = True
 otherwise = search x ys
bsearch
bsearch :: Int > [Int] > Bool
bsearch x [] = False
bsearch x list
 x == mid_val = True
 x < mid_val = bsearch x (take mid_index list)
 otherwise = bsearch x (drop (mid_index + 1) list)
where mid_index = div (length list) 2
mid_val = list !! mid_index
qsort
qsort :: [Int] > [Int]
qsort [] = []
qsort (pivot:others) = (qsort lowers) ++ [pivot] ++ (qsort highers)
where lowers = filter (<pivot) others
highers = filter (>=pivot) others
merge sort, msort
msort :: [Int] > [Int]
msort [] = []
msort [x] = [x]
msort xs = merge (msort lefts) (msort rights)
where lefts = take mid_index xs
rights = drop mid_index xs
mid_index = (length xs) `div` 2
merge :: [Int] > [Int] > [Int]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
 x < y = x:merge xs (y:ys)
 otherwise = y:merge (x:xs) ys
treesort
data Tree a = Empty  Node (Tree a) a (Tree a)
treesort:: Ord a => [a] > [a]
treesort xs = tree_inorder (list_to_bst xs)
list_to_bst:: Ord a => [a] > Tree a
list_to_bst [] = Empty
list_to_bst (x:xs) = bst_insert x (list_to_bst xs)
bst_insert:: Ord a => a > Tree a > Tree a
bst_insert i Empty = Node Empty i Empty
bst_insert i (Node l v r)
 i <= v = (Node (bst_insert i l) v r)
 i > v = (Node l v (bst_insert i r))
tree_inorder:: Tree a > [a]
tree_inorder Empty = []
tree_inorder (Node l v r) = tree_inorder l ++ (v:(tree_inorder r))
set equal
takes two lists of integers and checks if they are made from the same set of distinct elements.
import Data.List
setEq :: [Int] > [Int] > Bool
setEq xs ys = sort (nub xs) == sort (nub ys)
freqs
e.g.
Main> freqs [2,2,1,3,4,4,4]
[1,2,1,3]
import Data.List
freqs :: [Int] > [Int]
freqs xs = map length group_res
where group_res = group (sort xs)
longestPrefix
returns the longest common prefix of two lists. ie: When applied to "extras" and "extreme", the function should return "extr".
longestPrefix :: Eq a => [a] > [a] > [a]
longestPrefix [] _ = []
longestPrefix _ [] = []
longestPrefix (x:xs) (y:ys)
 x == y = x:(longestPrefix xs ys)
 otherwise = []
list builtins
length
computes the number of elements in a listreverse
reverse a listnull
returns True if a list is empty, and False otherwise the
!!
operator gets the nth element of a list, as in[1,2,3,4] !! 2
, which gives us3
(note zerobased list indexing).  the
++
operator joins two lists together, as in[1,2] ++ [3,4]
, which gives us[1,2,3,4]
head
and tail
separate a list into its first and remaining elements:
1 [2, 3, 4, 5, 6, 7, 8, 9, 10]
head ' <tail>
last
and init
do just the opposite:
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10
<init> ' last
take n
and drop n
split the list at an arbitrary point. For example, using 4 for n:
[1, 2, 3, 4] [5, 6, 7, 8, 9, 10]
<take 4> <drop 4>
zip
已集成。 zip :: [a] > [b] > [(a, b)]
zip
takes two lists and returns a list of pairs of elements, where the elements in each pair share the same list index.
dot xs ys = sum [x*y  (x, y) < zip xs ys]
concat
concat [[1, 2, 3], [4, 5], [6], []]
replicate
replicate :: Int > a > [a]
replicate 4 True
[True,True,True,True]
concatMap
>>> concatMap (take 3) [[1..], [10..], [100..], [1000..]]
[1,2,3,10,11,12,100,101,102,1000,1001,1002]
Data.List builtins
import Data.List
group
separates a list into sublists of adjacent, matching numbers. For example,group [1,1,3,3,2,1]
gives[[1,1],[3,3],[2],[1]]
.nub
removes all duplicates from a list. That is,nub [1,1,3,3,2,1]
gives[1,3,2]
.delete x
removes the first occurrence of x from a list. For example,delete 3 [2,3,4,3]
gives[2,4,3]
. The operator
\\
deletes each of the elements of one list from another list:[1,2,3,2] \\ [2,1]
gives[3,2]
. map
map (\e > e*e) x
dropWhile
dropWhile p xs returns the suffix remaining after takeWhile p xs. Warning: 一旦条件不满足，则dropWhile的drop操作停止，其余的不做判断全部返回
>>> dropWhile (< 3) [1,2,3,4,5,1,2,3]
[3,4,5,1,2,3]
>>> dropWhile (< 9) [1,2,3]
[]
>>> dropWhile (< 0) [1,2,3]
[1,2,3]
 span 基于一个条件，分离一个list成为两个表的元组，不成立的在后.
>>> span (< 3) [1,2,3,4,1,2,3,4]
([1,2],[3,4,1,2,3,4])
>>> span (< 9) [1,2,3]
([1,2,3],[])
>>> span (< 0) [1,2,3]
([],[1,2,3])
排列组合
Combination
λ> combinations 3 "abcdef"
["abc","abd","abe",...]
combinations :: Int > [a] > [[a]]
combinations 0 _ = [[]]
combinations n xs = [ xs !! i : x  i < [0..(length xs)1]
, x < combinations (n1) (drop (i+1) xs) ]
数学:
import Prelude
choose :: Integer > Integer > Integer
choose x y = div (product [1..x]) ((product [1..y]) * (product [1..(x  y)]))
用法:
Main> choose 6 3
20
Sort By
Sorting a list of lists according to length of sublists
λ> lsort ["abc","de","fgh","de","ijkl","mn","o"]
["o","de","de","mn","abc","fgh","ijkl"]
import List
lsort :: [[a]] > [[a]]
lsort = sortBy (\xs ys > compare (length xs) (length ys))
评论区