---
# System prepended metadata

title: Haskell
tags: [language]

---


# Resources
https://repl.it/languages/haskell
http://learnyouahaskell.com/chapters
http://book.realworldhaskell.org/read/
https://hoogle.haskell.org/ (可以按type搜索函数)
https://www.seas.upenn.edu/~cis194/fall16/index.html
https://www.seas.upenn.edu/~cis552/15fa/schedule.html


https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems
http://cheatsheet.codeslower.com/CheatSheet.pdf

[**haskell ecosystem**](https://github.com/Gabriella439/post-rfc/blob/main/sotu.md)

# How to run
在ghci里用 :load xxx.hs 加载脚本
long comment: {-  -}
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/using.html

https://www.cis.upenn.edu/~cis1940/fall16/lectures/05-real-world-haskell.html

# Basics

函数是最高优先级的运算符，注意括号

```haskell
>ghci succ 9 * 10
100
>ghci succ (9 * 10)
91
```

为了便于理解，函数也可以通过infix方式使用
```haskell
>ghci 92 `div` 10
>ghci 9
```

定义和调用函数
```haskell
>ghci doubleMe x = x + x
>ghci doubleMe 9
18
>ghci doubleUs x y = x*2 + y*2 
>ghci doubleUs 4 9
26
```

Apostrophe doesn't have any special meaning in Haskell's syntax. It's a valid character to use in a function name


[1,2,3] is just syntactic sugar for 1:2:3:[]
数组、字符串append: ++

 

开头添加元素, 使用：, O(1)
```haskell
ghci> 'A':" SMALL CAT" 
"A SMALL CAT" 
ghci> 5:[1,2,3,4,5] 
[5,1,2,3,4,5]
```


数组索引
```haskell
ghci> [9.4,33.2,96.2,11.2,23.25] !! 1 
33.2 
```

数组比较：lexicographic顺序


```haskell
ghci> let a = [5,4,3,2,1]
ghci> head a  
5   
ghci> tail a  
[4,3,2,1] 
ghci> last a    -- 注意
1  
ghci> init a    -- 注意
[5,4,3,2]
ghci> length a
5
ghci> reverse a --注意
[1,2,3,4,5]
ghci> take 3 a   
[5,4,3]
ghci> drop 2 a  --注意
[3,2,1]
ghci> minimum a
1
ghci> maximum a
5
ghci> sum a
15
ghci
ghci> null [1,2,3]  
False  
ghci> null []  
True
ghci> sum [5,2,1,6,3,2,5,7]  
31  
ghci> product [6,2,1,2]  
24    
ghci> 4 `elem` [3,4,5,6]  
True  
ghci> 10 `elem` [3,4,5,6]  
False  
```

ranges
```haskell
ghci> [1..20] 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] 
ghci> ['a'..'z'] 
"abcdefghijklmnopqrstuvwxyz" 
ghci> ['K'..'Z'] 
"KLMNOPQRSTUVWXYZ"
ghci> [2,4..20]  
[2,4,6,8,10,12,14,16,18,20]  
ghci> [3,6..20]  
[3,6,9,12,15,18]
```


cycle
```haskell
ghci> take 10 (cycle [1,2,3])  
[1,2,3,1,2,3,1,2,3,1]  
ghci> take 12 (cycle "LOL ")  
"LOL LOL LOL " 
ghci> take 10 (cycle [5])  
[5,5,5,5,5,5,5,5,5,5]
ghci> take 10 (repeat 5)  
[5,5,5,5,5,5,5,5,5,5]
```

list comprehension
```haskell
ghci> [x*2 | x <- [1..10]]  
[2,4,6,8,10,12,14,16,18,20]
ghci> [ x | x <- [50..100], x `mod` 7 == 3]  
[52,59,66,73,80,87,94]   
```

fst,snd,zip
```haskell
ghci> fst ("Wow", False)  
"Wow"  
ghci> snd ("Wow", False)  
False
ghci> zip [1,2,3,4,5] [5,5,5,5,5]  
[(1,5),(2,5),(3,5),(4,5),(5,5)] 
```

# Type/Typeclass
The [Char] type is synonymous with String
Integer: 大整数
Int: 32位整数

用":t"函数获取类型
```haskell
ghci> :t (True, 'a')  
(True, 'a') :: (Bool, Char)  
ghci> :t 4 == 5  
4 == 5 :: Bool 
ghci> :t head  
head :: [a] -> a 
ghci> :t fst  
fst :: (a, b) -> a 
ghci> :t "asdsd" --字符串的类型是字符数组
"asdsd" :: [Char]
```

函数类型声明, 如果使用ghci, 类型声明和定义应在一行, 用";"隔开
```haskell
removeNonUppercase :: [Char] -> [Char]  
removeNonUppercase st = [ c | c <- st, c `elem` ['A'..'Z']] 
```

Typeclass. 查看一个类型遵从哪些typeclass可以用:info或者:i
```haskell
ghci> :t (==)  
(==) :: (Eq a) => a -> a -> Bool
ghci> :t (>)  
(>) :: (Ord a) => a -> a -> Bool 
ghci> :t read  
read :: (Read a) => String -> a 
ghci> :t show
show :: Show a => a -> String
ghci> :t minBound
minBound :: Bounded a => a
ghci> :t 20  
20 :: (Num t) => t  
```

Show的member可以用字符串表示. 用"show"函数. 反之从字符串读取用"read"函数. 类型不明的时候, 指定类型
```haskell
ghci> show 3  
"3"  
ghci> show 5.334  
"5.334"  
ghci> show True  
"True"  
ghci> read "8.2" + 3.8  
12.0  
ghci> read "5" - 2  
3  
ghci> read "[1,2,3,4]" ++ [3]  
[1,2,3,4,3] 
ghci> read "5"
*** Exception: Prelude.read: no parse
ghci> read "5" :: Int  
5  
ghci> read "5" :: Float  
5.0  
ghci> minBound :: Int  
-2147483648  
ghci> maxBound :: Char  
'\1114111' 
```

# Function Syntax
## case表达式格式
```haskell
case expression of pattern -> result  
                   pattern -> result  
                   pattern -> result
```
```haskell
head' :: [a] -> a  
head' xs = case xs of [] -> error "No head for empty lists!"  
                      (x:_) -> x  --注意括号使用
                      
-- The x:xs pattern is used a lot, especially with recursive functions                      
```

定义多case函数时可以直接写多行，不用case表达。
调用时按照顺序从上到下扫描，所以**顺序matters**！

推论：定义递归函数时，base case必须在最上面

```haskell
sayMe :: (Integral a) => a -> String  
sayMe 1 = "One!"  
sayMe 2 = "Two!"  
sayMe 3 = "Three!"  
sayMe 4 = "Four!"  
sayMe 5 = "Five!"  
sayMe x = "Not between 1 and 5" 
```
模式匹配可能失败，所以需要catch all case放在最后
```haskell
charName :: Char -> String  
charName 'a' = "Albert"  
charName 'b' = "Broseph"  
charName 'c' = "Cecil"  
charName  x  = "unseen"  --catch all term
```

```haskell
addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a) 
addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2) 

tell :: (Show a) => [a] -> String  
tell [] = "The list is empty"  
tell (x:[]) = "The list has one element: " ++ show x  -- 可以写成 tell [x]
tell (x:y:[]) = "The list has two elements: " ++ show x ++ " and " ++ show y  -- 可以写成 tell [x,y]
tell (x:y:_) = "This list is long. The first two elements are: " ++ show x ++ " and " ++ show y
```
使用 name@ 来refer整体
```haskell
capital :: String -> String  
capital "" = "Empty string, whoops!"  
capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x] 
```

## guards
多条件检验: guards. 条件用pipe分割，最后otherwise.
if-else, case, guards等价 https://stackoverflow.com/questions/9345589/guards-vs-if-then-else-vs-cases-in-haskell
```haskell
--单参数
bmiTell :: (RealFloat a) => a -> String  
bmiTell bmi  
    | bmi <= 18.5 = "You're underweight, you emo, you!"  
    | bmi <= 25.0 = "You're supposedly normal. Pffft, I bet you're ugly!"  
    | bmi <= 30.0 = "You're fat! Lose some weight, fatty!"  
    | otherwise   = "You're a whale, congratulations!"
    
--多参数
bmiTell :: (RealFloat a) => a -> a -> String  
bmiTell weight height  
    | weight / height ^ 2 <= 18.5 = "You're underweight, you emo, you!"  
    | weight / height ^ 2 <= 25.0 = "You're supposedly normal. Pffft, I bet you're ugly!"  
    | weight / height ^ 2 <= 30.0 = "You're fat! Lose some weight, fatty!"  
    | otherwise                 = "You're a whale, congratulations!" 

--减少重复
bmiTell :: (RealFloat a) => a -> a -> String  
bmiTell weight height  
    | bmi <= skinny = "You're underweight, you emo, you!"  
    | bmi <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"  
    | bmi <= fat    = "You're fat! Lose some weight, fatty!"  
    | otherwise     = "You're a whale, congratulations!"  
    where bmi = weight / height ^ 2  
          skinny = 18.5  
          normal = 25.0  
          fat = 30.0  
          
--上面的where也可以写成          
where bmi = weight / height ^ 2  
      (skinny, normal, fat) = (18.5, 25.0, 30.0)          
          
--在where中定义函数
calcBmis :: (RealFloat a) => [(a, a)] -> [a]  
calcBmis xs = [bmi w h | (w, h) <- xs]  
    where bmi weight height = weight / height ^ 2
```

## let语句
let语句本身是expression
```haskell
ghci> 4 * (let a = 9 in a + 1) + 2  
42  
ghci> [let square x = x * x in (square 5, square 3, square 2)]  
[(25,9,4)]  
ghci> (let a = 100; b = 200; c = 300 in a*b*c, let foo="Hey "; bar = "there!" in foo ++ bar)  
(6000000,"Hey there!")  
```
在list comprehension中使用let
```haskell
calcBmis :: (RealFloat a) => [(a, a)] -> [a]  
calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0] 
```
as-pattern:The @ symbol is used to give a name to a parameter and to match against a pattern after the @ symbol.
```haskell
f (x:xs)               = x:x:xs
--可写为
f s@(x:xs)             = x:s

ghci> let a @ (b @ (Just c), Just d) = (Just 1, Just 2) in (a, b, c, d)
((Just 1,Just 2),Just 1,1,2)
```
# 自定义类型
等号后面的部份是value constructor. Value constructors的实质是函数, 返回类型是定义的类型.
```haskell
data Bool = False | True

data Shape = Circle Float Float Float | Rectangle Float Float Float Float 

--调用Circle或Rectangle创建出来的东西是Shape类型
ghci> :t Circle  
Circle :: Float -> Float -> Float -> Shape  
ghci> :t Rectangle  
Rectangle :: Float -> Float -> Float -> Float -> Shape 
```
注意，Shape是Type, 但Circle和Rectangle是函数不是Type. 所以不能定义为Circle->Float.
```haskell
surface :: Shape -> Float  
-- use the constructor for pattern matching
surface (Circle _ _ r) = pi * r ^ 2  
surface (Rectangle x1 y1 x2 y2) = (abs $ x2 - x1) * (abs $ y2 - y1) 
```

如果直接调用Circle 10 20 5会报错，因为尚不支持show函数。末尾添加"deriving (Show)".
```haskell
data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)
ghci> Circle 10 20 5  
Circle 10.0 20.0 5.0  
ghci> Rectangle 50 230 60 90  
Rectangle 50.0 230.0 60.0 90.0 
```

由于value constructor是函数，所以可以partial调用，再用map
```haskell
ghci> map (Circle 10 20) [4,5,6,6]  
[Circle 10.0 20.0 4.0,Circle 10.0 20.0 5.0,Circle 10.0 20.0 6.0,Circle 10.0 20.0 6.0]  
```

上面的定义可以重写为
```haskell
data Point = Point Float Float deriving (Show)  
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)
```
⚠️写函数参数的时候把constructor放进去！通过pattern matching定义多种行为。
```haskell
surface :: Shape -> Float  
surface (Circle _ r) = pi * r ^ 2  
surface (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 - x1) * (abs $ y2 - y1) 
```

Record语法
```haskell
data Person = Person String String Int Float String String deriving (Show) 

firstName :: Person -> String  
firstName (Person firstname _ _ _ _ _) = firstname  
  
lastName :: Person -> String  
lastName (Person _ lastname _ _ _ _) = lastname  
  
age :: Person -> Int  
age (Person _ _ age _ _ _) = age  
  
height :: Person -> Float  
height (Person _ _ _ height _ _) = height  
  
phoneNumber :: Person -> String  
phoneNumber (Person _ _ _ _ number _) = number  
  
flavor :: Person -> String  
flavor (Person _ _ _ _ _ flavor) = flavor 

```
上面的可以用record语法简洁地表达出来。上列函数自动创建。
```haskell
data Person = Person { firstName :: String  
                     , lastName :: String  
                     , age :: Int  
                     , height :: Float  
                     , phoneNumber :: String  
                     , flavor :: String  
                     } deriving (Show) 
```

使用record语法后，创建新变量时使用named参数，顺序可以变
```haskell
data Car = Car {company :: String, model :: String, year :: Int} deriving (Show)  

ghci> Car {company="Ford", model="Mustang", year=1967}  
Car {company = "Ford", model = "Mustang", year = 1967}  
```

参数化是haskell的一种polymorphism机制。
```haskell
data IList = INil | ICons Int  IList
data CList = CNil | CCons Char CList
data DList = DNil | DCons Double DList

-- 可以写为
data List a = Nil | Cons a (List a)
```



```haskell
data Vector a = Vector a a a deriving (Show)  
  
vplus :: (Num t) => Vector t -> Vector t -> Vector t  
(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)  
  
vectMult :: (Num t) => Vector t -> t -> Vector t  
(Vector i j k) `vectMult` m = Vector (i*m) (j*m) (k*m)  
  
scalarMult :: (Num t) => Vector t -> Vector t -> t  
(Vector i j k) `scalarMult` (Vector l m n) = i*l + j*m + k*n 
```
使用Emum
```haskell
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday   
           deriving (Eq, Ord, Show, Read, Bounded, Enum) 
     
ghci> Wednesday  
Wednesday  
ghci> show Wednesday  
"Wednesday"  
ghci> read "Saturday" :: Day  
Saturday  
ghci> Saturday == Saturday  
True  
ghci> Saturday > Friday  
True  
ghci> Monday `compare` Wednesday  
LT  
ghci> succ Monday  
Tuesday  
ghci> pred Saturday  
Friday  
ghci> [Thursday .. Sunday]  
[Thursday,Friday,Saturday,Sunday]  
ghci> [minBound .. maxBound] :: [Day]  
[Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]            
```

递归数据类型
``` haskell
-- Cons可以换成其他名字，如":-:"
data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord) 
--infixr, infixl 定义fixity
infixr 5 :-:  
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord) 
--record语法
data List a = Empty | Cons { listHead :: a, listTail :: List a} deriving (Show, Read, Eq, Ord)
```
例子：二叉搜索树
```haskell
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)  

singleton :: a -> Tree a  
singleton x = Node x EmptyTree EmptyTree  
  
treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
    | x == a = Node x left right  
    | x < a  = Node a (treeInsert x left) right  
    | x > a  = Node a left (treeInsert x right) 

treeElem :: (Ord a) => a -> Tree a -> Bool  
treeElem x EmptyTree = False  
treeElem x (Node a left right)  
    | x == a = True  
    | x < a  = treeElem x left  
    | x > a  = treeElem x right 
```

# TypeClass
定义接口。

**instance** is for making our types instances of typeclasses.

Eq的定义中使用了mutual recursion：简化了instance的实现. 否则只写一整套等于关系不够, 还得写一套不等于的.

```haskell
class Eq a where  
    (==) :: a -> a -> Bool  
    (/=) :: a -> a -> Bool  
    x == y = not (x /= y)  
    x /= y = not (x == y)  

data TrafficLight = Red | Yellow | Green 
instance Eq TrafficLight where  
    Red == Red = True  
    Green == Green = True  
    Yellow == Yellow = True  
    _ == _ = False
    
instance Show TrafficLight where  
    show Red = "Red light"  
    show Yellow = "Yellow light"  
    show Green = "Green light"    
```

类型可以subcless, Num是Eq的subclass. 以下相当于class Num a where, only we state that our type a must be an instance of Eq.
```haskell
class (Eq a) => Num a where  
   ...    
```

You can't have a function of the type a -> Maybe but you can have a function of a -> Maybe a or Maybe Int -> Maybe String
```haskell
instance (Eq m) => Eq (Maybe m) where  
    Just x == Just y = x == y  
    Nothing == Nothing = True  
    _ == _ = False  
```

# 高阶函数
map pattern
```haskell
shout::[Char]->[Char]
shout [] = []
shout (c:cs) = toUpper c : shout cs

squares :: [Int]->[Int]
squares  [] =  [] 
squares (h:t) =(h*h):squares t

--上面的两个函数明显有重复
mymap::(a -> b) -> [a] -> [b]
mymap f [] = []
mymap f (c:cs) = f c : mymap f cs
```
reduction pattern
```haskell
sumList ::[Int]->Int
sumList [] = 0 --base case 0, operation +
sumList (x:xs) = x + (sumList xs)

catList ::[String]->String
catList [] = "" --base case "", operation ++
catList (x:xs) = x ++ (catList xs)

--上面的两个函数明显有重复
foo op b [] = b  --b: base case
foo op b (x:xs)  = op x (foo op b xs)

sumList' xs = foo (+) 0 xs
catList' xs = foo (++) "" xs
```
在haskell中，相同的函数的相同参数可以cancel
```haskell
foo x y z =  bar x y z 
--相当于
foo = bar
--推论
shout   = mymap toUpper
squares = mymap (\h -> h * h) 
```

partial函数调用的结果是函数
```haskell
multThree :: (Num a) => a -> a -> a -> a  
multThree x y z = x * y * z  

ghci> let multTwoWithNine = multThree 9  
ghci> multTwoWithNine 2 3  
54  
ghci> let multWithEighteen = multTwoWithNine 2  
ghci> multWithEighteen 10  
180  
```

zipWith
```haskell
ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]  
[6,8,7,9]  
ghci> zipWith' max [6,3,2,1] [7,3,1,5]  
[7,3,2,5]  
ghci> zipWith' (++) ["foo ", "bar ", "baz "] ["fighters", "hoppers", "aldrin"]  
["foo fighters","bar hoppers","baz aldrin"]
```
⚠️：[foldr和foldl的区别](https://gist.github.com/CMCDragonkai/9f5f75118dda10131764)

```haskell
foldr::(a->b->b)->b->[a]->b
foldr op base [] = base
foldr op base (x:xs) = op x (foldr op base xs)

foldr op b (a1:a2:a3:a4:[])
=>
a1 `op` (a2 `op` (a3 `op` (a4 `op` b)))  

foldl op b (a1:a2:a3:a4:[])
=>
(((b `op` a1) `op` a2) `op` a3) `op` a4
--(((b `op` a4) `op` a3) `op` a2) `op` a1
--由于 a4 `op` b 的结果可以和a3结合, op的类型是a->b->b
```

foldl和foldl'的区别：
seq forces its 1st argument to be evaluated, then returns its 2nd argument. It doesn't actually do anything with the 1st argument: seq exists solely as a way to force that value to be evaluated.
http://book.realworldhaskell.org/read/functional-programming.html#id594142
```haskell
foldl f base []     = base
foldl f base (x:xs) = let base' = base `f` x 
                    in foldl f base' xs

foldl' f base []    = base
foldl' f base (x:xs) = let base' = base `f` x 
                     in seq base' $ foldl' f base' xs
                     
ghci> :type seq
seq :: a -> t -> t
```

scanl和scanr类似foldl/foldr，但是输出中间结果
```haskell
ghci> scanl (+) 0 [3,5,2,1]  
[0,3,8,10,11]  
ghci> scanr (+) 0 [3,5,2,1]  
[11,8,3,1,0]  
ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]  
[3,4,5,5,7,9,9,9]  
ghci> scanl (flip (:)) [] [3,2,1]  
[[],[3],[2,3],[1,2,3]] 
```

$: function application
```haskell
ghci> :t ($)
($) :: (a -> b) -> a -> b
ghci> sqrt $ 3 + 4 + 9 --右侧的表达式被用于左侧函数的参数
4.0
ghci> ($ 3) (4+)
7
ghci> ($) (4+) 3
7
ghci> (4+) $ 3
7

ghci> map ($ 3) [(4+), (10*), (^2), sqrt]  
[7.0,30.0,9.0,1.7320508075688772] 
```
dot: 复合函数
```haskell
ghci> map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]  
[-5,-3,-6,-7,-3,-2,-19,-24]  
ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]  
[-5,-3,-6,-7,-3,-2,-19,-24] 
ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]  
[-14,-15,-27] 

fn x = ceiling (negate (tan (cos (max 50 x))))
fn = ceiling . negate . tan . cos . max 50  
```
map是fmap的特例
```haskell
ghci> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
ghci> :t map
map :: (a -> b) -> [a] -> [b]
```
https://stackoverflow.com/questions/13134825/how-do-functors-work-in-haskell

# IO

类似于Recipe, 描述如何产生类型a的data, 通过Main函数执行后得到data. do语句组合多个recipe

to get the value out of an I/O action, you have to perform it inside another I/O action by binding it to a name with <-. 通过左箭头命名Recipe的结果以使用.

putStrLn的输入是String，返回结果类型是()的I/O动作。()是空tuple。空tuple的值和类型都是()。

```haskell
ghci> :t putStrLn  
putStrLn :: String -> IO ()  
ghci> :t putStrLn "hello, world"  
putStrLn "hello, world" :: IO () 
```
空IO:
```haskell
return ()
```
sequence
```haskell
main = do  
    a <- getLine  
    b <- getLine  
    c <- getLine  
    print [a,b,c]

--sequence :: [IO a] -> IO [a]
--上面的相当于
main = do  
    rs <- sequence [getLine, getLine, getLine]  
    print rs
    
ghci> sequence (map print [1,2,3])  
1  
2  
3  
[(),(),()] 
```
mapM: map和sequence二合一. ⚠️[mapM和mapM_的区别](https://stackoverflow.com/questions/27609062/what-is-the-difference-between-mapm-and-mapm-in-haskell/27609146)。
```haskell
ghci> mapM print [1,2,3]  
1  
2  
3  
[(),(),()]  
ghci> mapM_ print [1,2,3]  
1  
2  
3 
```
print的输入是Show类型的参数，相当于putStrLn . show
```haskell
show :: Show a => a -> String
print :: Show a => a -> IO ()
```

# Functor, Applicative
http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

## Functor
应用函数到wrapped值。
<$>是fmap的infix版本。
https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Functor.html#t:Functor
```haskell
fmap:: (a->b)->t a->t b

(<$>) :: (Functor f) => (a -> b) -> f a -> f b  
f <$> x = fmap f x  
```

## Applicative
wrapped函数应用到wrapped值。
https://hackage.haskell.org/package/base-4.14.0.0/docs/Control-Applicative.html#g:1
[Do Notation Equivalent](https://simonmar.github.io/bib/papers/applicativedo.pdf)
<*>在Control.Applicative中定义。
pure: takes a value and puts it in a minimal default context that still holds that value
```haskell
class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b 
```   
## Applicative例子：Maybe
```haskell     
instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something  

ghci> (Just (+3) <*> Just 2) == (Just 5)
True
ghci> [(*2), (+3)] <*> [1, 2, 3]
[2, 4, 6, 4, 5, 6]

ghci> (*) <$> Just 5 <*> Just 3 -- (fmap (*) Just 5) <*> Just 3)
Just 15
ghci> (/) <$> Just 5 <*> Just 3
Just 1.6666666666666667
ghci> Just (/2) <*> Just 5
Just 2.5
ghci> Just (2/) <*> Just 5
Just 0.4
```

## Applicative例子：列表
``` haskell
instance Applicative [] where  
    pure x = [x]  
    fs <*> xs = [f x | f <- fs, x <- xs] --所有函数 map 到所有值, f1 map完所有值, f2再map所有值...
    
ghci> [(*0),(+100),(^2)] <*> [1,2,3]  
[0,0,0,101,102,103,1,4,9] 
ghci> [(+),(*)] <*> [1,2] <*> [3,4]  
[4,5,5,6,3,4,6,8] 
-- 相当于[(+1),(+2),(*1),(*2)] <*> [3,4]

ghci> (++) <$> ["ha","heh","hmm"] <*> ["?","!","."]  
["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."] 
```
Applicative style和list comprehension的关系
```haskell
ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]     
[16,20,22,40,50,55,80,100,110]  
ghci> (*) <$> [2,5,10] <*> [8,10,11]  
[16,20,22,40,50,55,80,100,110] 
ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]  
[55,80,100,110] 
```
## Applicative例子：IO
```haskell
instance Applicative IO where  
    pure = return  
    a <*> b = do  
        f <- a  
        x <- b  
        return (f x) 
        
myAction :: IO String  
myAction = (++) <$> getLine <*> getLine 
```

```haskell
liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c  
liftA2 f a b = f <$> a <*> b  

ghci> liftA2 (:) (Just 3) (Just [4])  
Just [3,4]  
ghci> (:) <$> Just 3 <*> Just [4]  
Just [3,4]  
```

```haskell
sequenceA :: (Applicative f) => [f a] -> f [a]  
sequenceA [] = pure []  
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs 

ghci> sequenceA [Just 3, Just 2, Just 1]  
Just [3,2,1]  
ghci> sequenceA [Just 3, Nothing, Just 1]  
Nothing  
ghci> sequenceA [(+3),(+2),(+1)] 3  
[6,5,4]  
ghci> sequenceA [[1,2,3],[4,5,6]]  
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]  
ghci> sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]  
[]  
```
# Monad
Monad: 应用返回wrapped值的函数到wrapped值。>>=类似于pipeline chaining操作。Monad都是applicative functor, even if the Monad class declaration doesn't say so.
http://ucsd-pl.github.io/cse230/lectures/lec-monads.html
```haskell
class Monad m where  
    return :: a -> m a  --和pure一个东西，就名字不同. takes something and wraps it in a monad
  
    (>>=) :: m a -> (a -> m b) -> m b  --bind, it takes a value with a context and feeds it to a function that takes a normal value but returns a monadic value.
  
    (>>) :: m a -> m b -> m b  --never implement it when making Monad instances
    x >> y = x >>= \_ -> y  
  
    fail :: String -> m a  --never use it explicitly in our code
    fail msg = error msg  
```
## Maybe Monad
```haskell   
instance Monad Maybe where  
    return x = Just x  
    Nothing >>= f = Nothing  
    Just x >>= f  = f x  
    fail _ = Nothing 

ghci> return "WHAT" :: Maybe String  
Just "WHAT"  
ghci> Just 9 >>= \x -> return (x*10)   --x取脱掉Just的值
Just 90  
ghci> Nothing >>= \x -> return (x*10)  
Nothing 
```

## Do Notation
not just for IO. In a do expression, every line is a monadic value
```haskell
e1 >>= \v1 ->
  e2 >>= \v2 ->
    e3 >>= \v3 ->
      e
      
---相当于

do v1 <- e1
   v2 <- e2
   v3 <- e3
   e

do {v1 <- e1;v2<- e2; v3<- e3; e}  
```


```haskell
foo :: Maybe String  
foo = Just 3   >>= (\x -> 
      Just "!" >>= (\y -> 
      Just (show x ++ y))) 
      
foo :: Maybe String  
foo = do  
    x <- Just 3  
    y <- Just "!"  
    Just (show x ++ y) 
```

```haskell
ghci> Just 9 >>= (\x -> Just (x > 8))  
Just True

marySue :: Maybe Bool  
marySue = do   
    x <- Just 9  
    Just (x > 8) 
```

## List Monad
```haskell
instance Monad [] where  
    return x = [x]  
    xs >>= f = concat (map f xs)  ---拼一起
    fail _ = []
    
--行为类似for循环

ghci> [3,4,5] >>= \x -> [x,-x]  
[3,-3,4,-4,5,-5]  

ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')] 

listOfTuples :: [(Int,Char)]  
listOfTuples = do  
    n <- [1,2]  
    ch <- ['a','b']  
    return (n,ch)  
    
ghci> [ (n,ch) | n <- [1,2], ch <- ['a','b'] ]  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')] 
```


## State Monad
http://brandon.si/code/the-state-monad-a-tutorial-for-the-confused/
https://wiki.haskell.org/State_Monad
```haskell
newtype State s a = State { runState :: s -> (a,s) } 
instance Monad (State s) where  
    return x = State $ \s -> (x,s)  
    (State h) >>= f = State $ \s -> let (a, newState) = h s  
                                        (State g) = f a  
                                    in  g newState 
                                    
get = \s -> (s, s) -- 不改变当前状态，得到当前状态 用法:s<-get
put s = \_ -> ((), s) -- 替换状态
modify f = \s -> ((), f s) -- Update the state

runState :: State s a -> s -> (a, s)
runState t s = t s

evalState :: State s a -> s -> a

execState :: State s a -> s -> s
```

```haskell
type Stack = [Int]  
  
pop :: Stack -> (Int,Stack)  
pop (x:xs) = (x,xs)  
  
push :: Int -> Stack -> ((),Stack)  
push a xs = ((),a:xs)

stackManip :: Stack -> (Int, Stack)  
stackManip stack = let  
    ((),newStack1) = push 3 stack  
    (a ,newStack2) = pop newStack1  
    in pop newStack2  
```
可以重写为
```haskell
import Control.Monad.State    
pop :: State Stack Int  
pop = State $ \(x:xs) -> (x,xs)  
  
push :: Int -> State Stack ()  
push a = State $ \xs -> ((),a:xs) 

  
stackManip :: State Stack Int  
stackManip = do  
    push 3  
    a <- pop  
    pop  
```
## Parser Monad 
http://hackage.haskell.org/package/polyparse-1.13/docs/Text-ParserCombinators-Poly-Parser.html#t:Parser

https://www.seas.upenn.edu/~cis552/15fa/lectures/Parsers.html

https://hackage.haskell.org/package/parsec-3.1.14.0/docs/Text-ParserCombinators-Parsec-Char.html

http://dev.stephendiehl.com/fun/002_parsers.html

https://hackage.haskell.org/package/polyparse-1.13/docs/src/Text.ParserCombinators.HuttonMeijer.html#many1
```haskell
(>>=) :: Parser t a -> (a -> Parser t b) -> Parser t b
(>>) :: Parser t a -> Parser t b -> Parser t b
return :: a -> Parser t a
fail :: String -> Parser t a
```

https://wiki.haskell.org/Parsing_a_simple_imperative_language

a <|> b will first try parser a and if it fails (but without actually consuming any input) then parser b will be used

```haskell
many1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m [a]Source#

--many1 p applies the parser p one or more times. Returns a list of the returned values of p.

word  = many1 letter
```

使用mapM(map+sequence)进行parsing.
```haskell
string::String->Parser string
string cs = mapM char cs
```
orElse <|>: 如果第一个parser失败，则不consume字符串，重新run第二个parser
```haskell
orElse :: Parser a -> Parser a -> Parser a
orElse p1 p2 = P (\cs -> 
  case runParser p1 cs of
    []  -> runParser p2 cs
    r1s -> r1s
  )
```
parsing failure和return []的区别
```
\s -> []           -- FAILURE
\s -> [([], s)]    -- return []
```

## Either 
```haskell
instance (Error e) => Monad (Either e) where  
    return x = Right x  -- 注意类型是Right 
    Right x >>= f = f x  
    Left err >>= f = Left err  
    fail msg = Left (strMsg msg) 
```
错误处理
```haskell
evalEither :: Expr -> Either Expr Int
evalEither = eval
  where
    eval (Number n)    = return n
    eval (Plus  e1 e2) = do n1 <- eval e1 
                            n2 <- eval e2
                            return (n1 + n2)
    eval (Div   e1 e2) = do n1 <- eval e1 
                            n2 <- eval e2
                            if n2 /= 0 
                              then return (n1 `div` n2) 
                              else throwAnError e2
    eval (Def   e n)   = tryCatchError                -- try  
                           (eval e)                   --   { e }.        --evaluator
                           (\exn -> return n)         -- (exn) { ...}    --error handler


throwAnError = Left

tryCatchError :: Either e a -> (e -> Either e a) -> Either e a --second argument: error handler. if succeeds, produce Either e a type, so the handler has to do the same
tryCatchError (Right val) handler = Right val
tryCatchError (Left exn)  handler = handler exn
```

```haskell
class (Monad m) => MonadError e m | m -> e where
    throwError :: e             -- error to throw
               -> m a

    catchError :: m a           -- action to execute
               -> (e -> m a)    -- error handler
               -> m a
```
## transformer
```
-- >>> :t runExceptT 
-- runExceptT :: ExceptT e m a -> m (Either e a)
-- >>> :t runStateT 
-- runStateT :: StateT s m a -> s -> m (a, s)
```

## Random Generator
https://hackage.haskell.org/package/QuickCheck-2.13.2/docs/Test-QuickCheck-Gen.html
Gen是Monad
```haskell
elems::[a]->Gen a
elems xs =  do
  i <- choose (0, length xs)
  return (xs !! i)
  
posPr::do
posPr = do
  x <- pos
  y <- pos
  return (x, y)
  
randomThings::(Arbutrary a) => IO [a]
randomThings = sample' arbitrary
```

## 常用函数

liftM和fmap十分接近
```haskell
fmap :: (Functor f) => (a -> b) -> f a -> f b  
liftM :: (Monad m) => (a -> b) -> m a -> m b  

liftM :: (Monad m) => (a -> b) -> m a -> m b  
liftM f m = m >>= (\x -> return (f x)) 

liftM :: (Monad m) => (a -> b) -> m a -> m b  
liftM f m = do  
    x <- m  
    return (f x)  
```
ap类似<*>
```haskell
(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b  

ap :: (Monad m) => m (a -> b) -> m a -> m b  
ap mf m = do  
    f <- mf  
    x <- m  
    return (f x) 
```

join
```haskell
join :: (Monad m) => m (m a) -> m a  
join mm = do  
    m <- mm  
    m  
    
ghci> join (Just (Just 9))  
Just 9  
ghci> join [[1,2,3],[4,5,6]]  
[1,2,3,4,5,6]  
ghci> runState (join (State $ \s -> (push 10,1:2:s))) [0,0,0]  
((),[10,1,2,0,0,0]) 
```
filterM
```haskell
filter :: (a -> Bool) -> [a] -> [a]  
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]  
```
foldM
```haskell
foldl :: (a -> b -> a) -> a -> [b] -> a 
foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a 

binSmalls :: Int -> Int -> Maybe Int  
binSmalls acc x  
    | x > 9     = Nothing  
    | otherwise = Just (acc + x) 
    
ghci> foldM binSmalls 0 [2,8,3,1]  
Just 14  
ghci> foldM binSmalls 0 [2,11,3,1]  
Nothing  
```

## Monad Laws
return x >>= f is the same damn thing as f x
```haskell
ghci> return 3 >>= (\x -> Just (x+100000))  
Just 100003  
ghci> (\x -> Just (x+100000)) 3  
Just 100003 
ghci> return "WoM" >>= (\x -> [x,x,x])  
["WoM","WoM","WoM"]  
ghci> (\x -> [x,x,x]) "WoM"  
["WoM","WoM","WoM"] 
```
m >>= return is no different than just m
```haskell
ghci> Just "move on up" >>= (\x -> return x)  
Just "move on up"  
ghci> [1,2,3,4] >>= (\x -> return x)  
[1,2,3,4]  
ghci> putStrLn "Wah!" >>= (\x -> return x)  
Wah!  
```

Doing (m >>= f) >>= g is just like doing m >>= (\x -> f x >>= g)
```haskell
ghci> return (0,0) >>= landRight 2 >>= landLeft 2 >>= landRight 2  
Just (2,4)  
ghci> ((return (0,0) >>= landRight 2) >>= landLeft 2) >>= landRight 2  
Just (2,4)  
```

composition
f <=< (g <=< h) should be the same as (f <=< g) <=< h

```haskell
(.) :: (b -> c) -> (a -> b) -> (a -> c)  
f . g = (\x -> f (g x)) 

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> m c)  
f <=< g = (\x -> g x >>= f) 

ghci> let f x = [x,-x]  
ghci> let g x = [x*3,x*2]  
ghci> let h = f <=< g  
ghci> h 3  
[9,-9,6,-6]  
```

# module
```haskell
Map.fromList :: (Ord k) => [(k, v)] -> Map.Map k v  

ghci> Map.fromList [("betty","555-2938"),("bonnie","452-2928"),("lucille","205-2928")]  
fromList [("betty","555-2938"),("bonnie","452-2928"),("lucille","205-2928")]  
ghci> Map.fromList [(1,2),(3,4),(3,2),(5,5)]  
fromList [(1,2),(3,2),(5,5)] --重复被扔掉
 

ghci> Map.empty  
fromList []  
ghci> Map.insert 3 100 Map.empty  
fromList [(3,100)]  
ghci> Map.insert 5 600 (Map.insert 4 200 ( Map.insert 3 100  Map.empty))  
fromList [(3,100),(4,200),(5,600)]  
ghci> Map.insert 5 600 . Map.insert 4 200 . Map.insert 3 100 $ Map.empty  
fromList [(3,100),(4,200),(5,600)] 
```

###### tags: `language`