趣学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

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

字符串¶

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

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

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

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¶

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

addVector¶

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

head’¶

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

bmiTell¶

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

递归¶

略

快排

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

随机生成一个数字列表

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¶

定义

class Functor f where
    fmap :: (a -> b) -> f a -> f b

前面的随机数快排应用:

*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的逻辑:

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¶

main = putStrLn "Hello,world"

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

echo¶

main = do
    line <- getLine
    putStrLn line

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

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

一直echo:

main = forever $ do
    line <- getLine
    putStrLn line

其中forever的定义是这样的.

forever :: (Monad m) => m a -> m b
forever a = a >> forever a

每一次do块执行的结果不向后传递,重新执行这个do块.

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

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

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

计算过程通过栈的压栈出栈进行.

实现上面的过程

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

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

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

类型定义:

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的结构, 可以看到这样的例子.

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的一个结构问题. 例如:

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的定义:

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`实现:¶

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

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

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

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

一个有意思的例子:

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

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

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

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

`IO`的`Applicative`实现¶

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

引申出新的例子.

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

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

`ZipList`的`Applicative`实现¶

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)

这里模式匹配取值还挺简洁的. ZipList的结果使用getZipList取出来, 返回类型是[a].

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的值.

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

Contents

Previous topic

Next topic

This Page

趣学haskell¶

简单尝试¶

列表/元组操作示例¶

类型¶

常见类型¶

字符串¶

常见`typeclass`¶

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

例程¶

factorial¶

addVector¶

head’¶

bmiTell¶

递归¶

模块¶

定义类型/类型类¶

Functor¶

输入/输出¶

hello,world¶

echo¶

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

函数式解决问题¶

逆波兰计算器¶

`Functors`, `Applicative Functors`, `Monoids`¶

Functor¶

Applicative Functor¶

`Maybe`的`Applicative`实现:¶

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

`IO`的`Applicative`实现¶

`ZipList`的`Applicative`实现¶

`newtype`¶

Monoids¶

Contents

Previous topic

Next topic

This Page

趣学haskell¶

简单尝试¶

列表/元组操作示例¶

类型¶

常见类型¶

字符串¶

常见typeclass¶

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

例程¶

factorial¶

addVector¶

head’¶

bmiTell¶

递归¶

模块¶

定义类型/类型类¶

Functor¶

输入/输出¶

hello,world¶

echo¶

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

函数式解决问题¶

逆波兰计算器¶

Functors, Applicative Functors, Monoids¶

Functor¶

Applicative Functor¶

Maybe的Applicative实现:¶

[]的Applicative实现:¶

IO的Applicative实现¶

ZipList的Applicative实现¶

newtype¶

Monoids¶

常见`typeclass`¶

`Functors`, `Applicative Functors`, `Monoids`¶

`Maybe`的`Applicative`实现:¶

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

`IO`的`Applicative`实现¶

`ZipList`的`Applicative`实现¶

`newtype`¶