# 趣学haskell


@20190428

简单回顾笔记


## 简单尝试

- 表达式
    - 中缀/前缀
        - `1 + 1`
            - `(+) 1 1`
        - `f g 1`
            - `f $ g 1`
            - `$`调整优先级, 最右绑定
- 类型
- 函数定义
    - 类型签名
- `List`
    - 常用方法
    - 列表内包(`List comprehesion`)
        - `[x * x | x <- [1 .. 10]]`
        - 加过滤器
            - `[x * x | x <- [1 .. 10], x > 10]`
        - 多参列表
            - `[x * y  | x <- [1 .. 10], y <- [5 .. 20]]`
                - 笛卡儿积
- `元组`
    - `(1, 2)`
        - 多类型
    - `fst`/ `snd`
- 集合操作
    - `head` / `tail`
        - 类比于scheme中的`car`, `cdr`
    - `zip`
        - 向量点乘
            - 向量xs, ys, `map product $ zip xs ys`


### 列表/元组操作示例

参考文档
https://en.wikibooks.org/wiki/Haskell/Lists_and_tuples

```haskell
Prelude> -- Tuple
Prelude> let t = (1, "a")
Prelude> fst t
1
Prelude> snd t
"a"
Prelude> -- List
Prelude> let x = [(x,y) | x <-[1..3], y<- [2..5]]
Prelude> x
[(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)]
Prelude> head x
(1,2)
Prelude> tail x
[(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)]
Prelude> take 3 x
[(1,2),(1,3),(1,4)]
Prelude> drop 3 x
[(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)]
```


## 类型
@20190506

### 常见类型

- `Int`
    - `-2^n ~ (2 ^ n - 1)`
- `Integer`
    - 大整数
- `Float`
- `Double`


### 字符串

```haskell
Prelude> let s = "扶把"
Prelude> s
"\25206\25226"
Prelude> :t s
s :: [Char]
```

内码是`unicode`, 字符串的类型是`[Char]`

ghc还有其它的文本类型, `ByteString`, `Text`.
使用`{-# LANGUAGE OverloadedStrings #-}`来支持字符串字面量的多态.

```haskell
Prelude B> let s1 = "这种" :: B.ByteString

<interactive>:32:10: error:
    • Couldn't match expected type ‘B.ByteString’
                  with actual type ‘[Char]’
    • In the expression: "这种" :: B.ByteString
      In an equation for ‘s1’: s1 = "这种" :: B.ByteString
Prelude B> :set -XOverloadedStrings
Prelude B> let s1 = "这种" :: B.ByteString
Prelude B> s1
"\217\205"
Prelude B> :t s1
s1 :: B.ByteString
Prelude B> :t "foobar"
"foobar" :: Data.String.IsString p => p
```

常见用法

- 分词
    - `words`
        - `Prelude B> words "虚无 在x 字段"`
            - `["\34394\26080","\22312x","\23383\27573"]`
- 合并
    - `unwords`
        - `Prelude B> putStrLn $ unwords $ words "虚无 在x 字段"`
            - `虚无 在x 字段`
- 拼接(py, join)
    - `Data.List intercalate`
        - `intercalate "," ["a", "b", "c"]`
- 去空白
    - `Data.String.Utils`
        - `strip`
        - `lstrip`
        - `rstrip`

### 常见`typeclass`

- `Eq`
    - `==`, `\=`
- `Ord`
    - 必须是`Eq`
    - `>`, `<`, `>=`, `<=`, `compare`
- `Show`
    - `show`
- `Read`
    - `read`
- `Enum`
- `Bounded`
- `Num`
- `Integral`
- `Floating`

## 函数/高阶函数(high order)

- 定义
    - 模式匹配
        - 代数类型匹配值
            - @`factorial`
        - unpack 元组
            - @`addVector`
        - 列表匹配
            - @`head'`
                - `(x:xs)`
                - `(x:_)`
        - Guards
            - 带条件的匹配
            - @`bmiTell`
                - guard
                - let
                    - `let ... in ...`
                - where
        - case
            - `case exp of pattern -> r  ...`
- 高阶函数
    - 高阶的意思是输入为函数的函数, 函数的函数
    - 柯里化/非柯里化
        - 多参的函数
            - `a -> a -> a -> r`
                - 可以做柯里化, 部分绑定参数,形成新的函数
            - `(a, a) -> r`
                - 不能做柯里化
    - 例程
        - `zipWith`
        - `flip`
        - `map`
        - `filter`
        - `foldl`, `foldr`
            - reduce
        - `sum`
    - 函数`$`应用
        - 利用函数优先计算参数的规则, 优先计算右侧表达式
            - `(a -> b) -> a -> b`
            - `f $ x = f x`
    - 函数组合
        - `.`
            - `f . g = \x -> f (g x)`
- lambda
    - 匿名函数
        - `\x y -> x + y`
            - `let add = \x y -> x + y`
                - 柯里化
                    - `let add2 = add 2`
                        - `add2 3 = 5`

### 例程
#### factorial

```haskell
factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)
```

#### addVector

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

#### head'

```haskell
head' :: [a] -> a
head' [] = error "empty list"
head' (x:_) = x
```

### bmiTell

```haskell
bmiTell :: (RealFloat a) => a -> a -> String
bmiTell w h 
    | bmi <= skinny = "underweight"
    | bmi <= normal = "normal"
    | bmi <= fat    = "fat"
    | otherwise  = "whale"
    where bmi    = w / h ^ 2
          skinny = 18.5
          normal = 25.0
          fat    = 30.0
```

## 递归

略

快排
```haskell
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = 
    let lp = quicksort [a | a <- xs, a <= x]
        rp = quicksort [a | a <- xs, a > x]
    in lp ++ [x] ++ rp
```

随机生成一个数字列表
```haskell
import System.Random (randomRIO)
import Control.Monad (replicateM)

randomList :: Int -> IO [Int]
randomList n = replicateM n $ randomRIO (1,6)
```

测试用例
```
*Main System.Random Control.Monad> liftM quicksort $ randomList 20
[1,1,1,1,1,2,2,3,3,4,4,4,4,5,5,5,5,6,6,6]
```

## 模块

- 加载方式
    - `ghci`
        - `> :m + xx xx`
    - `import`
        - `import Data.List`
            - 全部加载
        - `import Data.List hiding (...)`
            - 排除部分名字
        - `import qualified Data.ByteString as B`
            - 别名
        - `import Data.List (...)`
            - 部分引入
- 定义新模块
    - `module Geometry where`
    - 指定导出符号
        - `module Geometry (volume, area) where`
    - 子模块
        - `module Geometry.Cube where`
- 常用模块
    - `Data.List`
        - `intersperse`
            - `intersperse '.' "MONKEY"`
                - `"M.O.N.K.E.Y"`
        - `transpose`
        - `intercalate`
            - py join
        - `concat`
        - `concatMap`
        - `and`
        - `or`
        - `any`
        - `all`
        - `iterate`
            - `take 10 $ iterate (*2) 1`
        - `splitA`
        - `takeWhile`
        - `dropWhile`
        - `span`
        - `sort`
        - `group`
        - `isPrefixOf`
        - `isSuffixOf`
        - `elem`
        - `notElem`
        - `partition`
        - ...
    - `Data.Char`
        - `isSpace`...`isLetter`...
    - `Data.Map`
        - `fromList`
            - `Map.fromList [("a", 1), ("b", 2) ...]`
        - `fromListWith`
        - `toList`
        - `empty`
            - 空map
        - `null`
            - 判空谓词
        - `size`
            - `len(m)`
        - `member`
            - 包含判定谓词
        - `lookup`
            - 查key, 返回`Just something`
        - `map`/`filter`
        - `keys`
        - `elems`
    - `Data.Set`
        - `fromList`
        - `difference`
        - `intersection`


## 定义类型/类型类

- 代数类型
    - `data Book = Book t0 t1 t2 | Booklet t0 t1 t2 deriving (Show, Ord)`
        - `Book/Booklet`即为构造子
    - record方式
        - `data Person = Person {name :: String, age :: Int} deriving (Show)`
            - 实例化
                - `Person {name="tom", age=10}`
            - 自动生成访问器
                - `> name p`
                    - tom
                - `> age p`
                    - 10
    - 类型变量
        - `data Maybe a = Nothing | Just a`
    
- type synonyms
    - 同义词/别名?
        - 两个类型等价,且可在场景中互换
            - `typedef`? 
        - `type String = [Char]`

- 递归数据结构
    - 数据定义时,调用自身构建子的数据类型
        - `data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)`
        - `data List a = Empty | Cons {listHead :: a, listTail :: List a} deriving (Show, Read, Eq, Ord)`
    - 示例
        - 列表
        - 二叉树
            - 遍历
    

### Functor

定义
```haskell
class Functor f where
    fmap :: (a -> b) -> f a -> f b
```

前面的随机数快排应用:
```haskell
*Main System.Random Control.Monad> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
*Main System.Random Control.Monad> :t liftM
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
```

`Maybe`实现`Functor`的逻辑:
```haskell
instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing  
```


## 输入/输出

所有IO相关的操作, 都是在操作Monad.

一些控制monad, `import Control.Monad`

- `sequence`
    - `sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)`
    - 一组操作串起来,并返回monad包装的结果
        - `sequence [getLine, getLine, getLine]`
- `when`
    - `when :: Applicative f => Bool -> f () -> f ()`
- `forever`
    - `forever :: Applicative f => f a -> f b`
- `mapM`
    - `mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)`
- `mapM_`
    - `mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()`


一些常用的例程.

### hello,world

```haskell
main = putStrLn "Hello,world"
```

`putStrLn`类型签名为`putStrLn :: String -> IO ()`

### echo

```haskell
main = do
    line <- getLine
    putStrLn line
```

`getLine`类型签名为`getLine :: IO String`.

`<-`用于从`IO`中获得值, 和`do block`一起使用.

一直`echo`:

```haskell
main = forever $ do
    line <- getLine
    putStrLn line
```

其中`forever`的定义是这样的.

```haskell
forever :: (Monad m) => m a -> m b
forever a = a >> forever a
```
每一次`do`块执行的结果不向后传递,重新执行这个`do`块.

一个`read-eval-print`循环的解释器界面也是这样写的. 


### pipeline, 逆序文件内容中的词, 然后输出

```haskell
import System.Environment
import System.IO

main = do
    args <- getArgs
    withFile (head args) ReadMode $ \h -> do
        x <- hGetContents h
        putStr $ reverseWords x

reverseWords :: String -> String
reverseWords = unwords . map reverse . words
```

上面的程序可以简化.


## 函数式解决问题

### 逆波兰计算器

分析逆波兰表达式

```
> 10 4 3 + 2 * -
> 2 3 +
> 10 4 3 + 2 * -
```
计算过程

List的头部作为栈顶.

```
s=[]
> 10 4 3 + 2 * -
s=[3,4,10]
> 10 (4 3 +) 2 * -
s=[2,7,10]
> 10 (7 2 *) -
s=[14,10]
> 10 14 -
> -4
```
计算过程通过栈的压栈出栈进行.

实现上面的过程

```haskell
import Data.List

solveRPN :: (Num a, Read a, Fractional a) => String -> a
solveRPN = head . foldl fn [] . words
    where fn (x:y:ys) "*" = (x * y) : ys
          fn (x:y:ys) "+" = (x + y) : ys
          fn (x:y:ys) "-" = (x - y) : ys
          fn (x:y:ys) "/" = (x / y) : ys
          fn xs strnum    = read strnum : xs
```

使用过程式的方式按上面思路计算过程如下:

```python
ops = {
    '*': lambda x,y:x*y,
    '/': lambda x,y:x/y,
    '+': lambda x,y:x+y,
    '-': lambda x,y:x-y,
}
def solve_rpn(s):
    toks = s.split()
    st = []
    for tok in toks:
        if tok in ('*', '/', '+', '-'):
            rhs = float(st.pop(0))
            lhs = float(st.pop(0))
            st.insert(0, ops[tok](lhs, rhs))
        else:
            st.insert(0, tok)
    return st[0]
```

## `Functors`, `Applicative Functors`, `Monoids`

### Functor

https://wiki.haskell.org/Functor

类型定义:
```haskell
class Functor fc where 
    fmap :: (a -> b) -> fc a -> fc b
    (<$) :: a -> f b -> fc a
```

- `Functor`
    - 使用上, 函子就是可以被map over的类型.
    - 换言之就是我们可以把`Functor`当做普通容器处理, 无论它是不是monad. 
        - `map (\x->x*2) [1,2,3]`
    - `Functor Law`
        - `fmap`函数`id`到一个Functor的结果,应该和`id`应用到这个Functor的结果一致.


根据`Functor`的结构, 可以看到这样的例子.

```haskell
main = do 
    line <- fmap (intersperse '-' . reverse . map toUpper) getLine  
    putStrLn line  
--- sep ---
main = do 
    line <- fmap (intersperse '-') (fmap reverse (fmap (map toUpper) getLine))  
    putStrLn line  
```

### Applicative Functor

`Applicative Functor`是加强版的Functor, 它的typeclass定义在`Control.Applicative`中. 

解决Functor的一个结构问题. 例如:

```haskell
Prelude> let a = fmap (*) [1,2,3,4]
Prelude> :t a
a :: Num a => [a -> a]
Prelude> fmap (\f -> f 9) a
[9,18,27,36]
```

如果`(\f -> f 9)`也是被Functor包装的,那么fmap就map不进去, 例如将`Just (3 *)` map over到`Just 5`上, 没有办法处理.多参数的函数fmap就会出现这种情况. 

观察`Applicative`的定义:

```haskell
class (Functor f) => Applicative f where -- 一个Applicative必须是首先是Functor
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
```

将其中的`<*>`和Functor定义中的`fmap`做比较, 它的定义就是将容器里的f, map到容器里的数据上.

上面的定义也是说, 一个Applicative既可以`fmap`一个普通函数进容器, 也可以`<*>`一个容器中的函数进入容器.


#### `Maybe`的`Applicative`实现:

```haskell
instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something
```

一种等价关系, `pure f <*> x`等于`fmap f x`.

#### `[]`的`Applicative`实现:

```haskell
instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
```

一个有意思的例子:

```haskell
ghci> (++) <$> ["ha", "heh", "hmm"] <*> ["?", "!", ".]
["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]
```

`<$>`后生成一个函数列表`[s -> s]`, 然后`<*>`进符号列表, 生成一组笛卡尔展开的字符串.

上面的例子可以扩展开来. 

```haskell
ghci > [x * y | x <- xs, y <- ys]
ghci > (*) <$> xs <*> ys
```

#### `IO`的`Applicative`实现

```haskell
instance Applicative IO where
    pure = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)
```

引申出新的例子.

```haskell
myAction :: IO String
myAction = do
    a <- getLine
    b <- getLine
    return $ a ++ b
```

可以改写成 `myAction = (++) <$> getLine <*> getLine`.

#### `ZipList`的`Applicative`实现

```haskell
instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)
```
这里模式匹配取值还挺简洁的. ZipList的结果使用`getZipList`取出来, 返回类型是`[a]`.

```haskell
ghci > getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100,100]
[101,102,103]
```

### `newtype`

- `data`
    - algebraic data type
- `type`
    - type synonyms
- `newtype`
    - 从现有的类型中定义出新的类型
    - 比`data`快,生气了拆包/装包的工作
        - 只能定义单一一个值构造子
    - 也可以用`deriving`
    - 惰性求值
        - `helloMe :: CoolBool -> String`
        - `data CoolBool = CoolBool { getCoolBool :: Bool }`
            - `helloMe undefined`
                - "*** Exception: Prelude.undefined"
        - `newtype CoolBool = CoolBool { getCoolBool :: Bool }`
            - `helloMe undefined`
                - "hello"
                - 体现laziness

### Monoids

一个`Monoid`(`Data.Monoid`)是一个满足结合律, 且有相对那个函数作为identity的值.

```haskell
class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty
```