learn-haskell

Posted on | In

—— Notes on CH8 Haskell, Seven Languages in Seven Weeks by Bruce A. Tate

引言

Haskell不同于Scala，是一门纯函数式语言，它强制使用者使用函数式语法而没有妥协。

  • 是一门强类型定义的静态类型语言。它的**类型模型基于推断理论（in-ferred）**并被公认为是函数语言中最高效的类型系统之一。你会发现该类型系统支持多态语义并有助于人们作出十分整洁清晰的设计。

  • 支持Erlang风格的模式匹配（pattern matching）和哨兵表达式。你也能在Haskell中发现Clojure风格的惰性求值（lazyevaluation）以及与Clojure和Erlang相同的列表推导语法。

  • 无副作用，通过monad概念保存状态：一个Haskell函数可以返回一个有副作用并且会被延迟执行的结果.

Day1 逻辑

在OS X下安装Haskell环境：brew install haskell-platform

通过命令启动交互式环境：ghci

基本类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
{- basic type -}

Prelude> 4 * (5 + 1)
24

Prelude> "hello" ++ " world"
"hello world"

Prelude> ['a', 'b'] --list
"ab"
['a', 'b'] :: [Char]

Prelude> (1,2,3) --tuple
(1,2,3) :: (Num t, Num t1, Num t2) => (t, t1, t2)

Prelude> if (5 == 5) then "true" else "false""true"
"true"

{- var accessing -}

fst tuple
snd tuple
head list
last list
tail list
let (h:t) = [1, 2, 3, 4] 	{- h=1, t=[2,3,4] -}
1:[2,3,4] 					{- [1,2,3,4] -}

{- verbose type info -}

Prelude> :set +t  	

Prelude> :t 2
2 :: Num a => a

Prelude> (5 == (2 + 3))
True
it :: Bool

D2 函数

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
{- let binding -}

Prelude> let x = 10
x :: Integer

Prelude> let double x = x * 2
double :: Num a => a -> a

{- dot notation -}
Prelude> let second = f . g
Prelude> let second list = f (g list)

second :: [a] -> a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
{- ./double.hs -}
module Main where
    {- without type def -}
    double x = x + x

    {- with type def -}
    double_int :: Integer -> Integer
    double_int x = x + x
    
{- load .hs in GHCi -}

*Main> :load double.hs
*Main> double 2
4

递归

1
2
3
4
5
6
7
8
Prelude> let fact x = if x == 0 then 1 else fact (x - 1) * x

{- ./fact_with_guards.hs -}
module Main where
	fact :: Integer -> Integer
	fact x
		| x > 1 = x * fact(x - 1)  {- sentinel -}
		| otherwise = 1

使用Tuple

1
2
3
4
5
6
{- ./fib_recusive.hs -}
module Main where
    fib :: Integer -> Integer
    fib 0 = 1
    fib 1 = 1
    fib x = fib(x - 1) + fib(x - 2)
1
2
3
4
5
6
7
8
9
10
11
{- ./fib_tuple.hs -}
module Main where
    fibFast :: Integer -> Integer
    fibFast x = fibResult(fibTuple(0,1,x))

    fibTuple :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
    fibTuple (x, y, 0) = (x, y, 0)
    fibTuple (x, y, index) = fibTuple (y, x + y, index - 1)

    fibResult ::  (Integer, Integer, Integer) -> Integer
    fibResult (x,y,z) = x
1
2
3
4
5
6
7
8
9
10
11
12
{- ./fib_pair.hs -}
module Main where
    {- using Tuple-}
    fibFast :: Integer -> Integer
    fibFast = fst . fibNthPair

    fibNextPair :: (Integer, Integer) -> (Integer, Integer)
    fibNextPair (x, y) = fibNextPair (y, x + y)

    fibNthPair :: Integer -> (Integer, Integer)
    fibNthPair 1 = (1,1)
    fibNthPair x = fibNextPair(fibNthPair(x-1))

遍历列表

通过let (h:t) = list

1
2
3
4
5
6
7
{- ./fib_pair.hs -}
module Main where
    size [] = 0
    size (h:t) = 1 + size (t)

    prod [] = 1
    prod (h:t) = h * prod (t)

生成列表

1:[2,3,4] -> [1,2,3,4]

偶数列表

1
2
3
4
module Main where
    allEven :: [Integer] -> [Integer]
    allEven [] = []
    allEven (h:t) = if even h then h:allEven t else allEven t

Range

1
2
3
[1..10]
[10, 8 .. 4]
take 5 [0, 2 ..]

List Derivation (like python)

1
2
3
4
[x * 2 | x <- [1,2,3]]
[(y,x+1) | (x,y) <-[(1,2),(2,3),(3,4)]]
let crew = ["Spock", "Kirk", "McCoy"]
[(a,b) | a <- crew, b <- crew, a/=b] {- /= means not equal -}

练习 乘法表

1
2
3
4
5
6
7
8
9
10
11
12
module Main where
    mulTable :: Integer -> [(Integer,Integer,Integer)]
    mulTable 1 = mulTableRow 1
    mulTable n = (mulTableRow n) ++ (mulTable (n-1))

    mulTableRow :: Integer -> [(Integer,Integer,Integer)]
    mulTableRow n = [(x,y,x*y) | x <- [n], y<-[1..n]]

{-
*Main> mulTable 2
[(2,1,2),(2,2,4),(1,1,1)]
-}

Day2

高阶函数

匿名函数

1
(\param1.. paramn ->function_body)
map
1
map (\x -> x * x) [1, 2, 3]
filter、foldl和foldr (reduce)
1
2
3
4
5
6
7
8
Prelude> filter odd [1, 2, 3, 4, 5]
[1,3,5]

Prelude> foldl (\x carryOver -> carryOver + x) 0 [1 .. 10]
55

Prelude> foldl1 (+) [1 .. 3]
6
where
1
2
3
4
5
6
{- haskell/map.hsmodule -}
module Main where
    squareAllPlusOne list = map squarePlusOne list
        where 
            squarePlusOne x = x * x + a
            let a = 1

柯里化

把多参数函数，拆分成多个只有一个参数的函数

1
2
3
4
5
6
7
8
Prelude> double x = x * x
double :: Num a => a -> a

Prelude> let prod x y = x * y
prod :: Num a => a -> a -> a

Prelude>  let double = prod 2
double :: Integer -> Integer

惰性求值

一个无尽序列
1
2
3
{- my_range.hs -}
module Main where
     myRange start step = start:(myRange (start + step) step)
惰性 Fib 数列
1
2
3
4
5
6
7
{- lazy_fib.hs -}
module Main where
    lazyFib x y = x:(lazyFib y (x + y))

    fib = lazyFib 1 1
    
    fibNth x = head (drop (x - 1) (take (x) fib))

Day3

类与类型

自定义类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
{- cards.hs -}
module Main where
    data Suit = Spades | Hearts deriving (Show)
    data Rank = Ten | Jack | Queen | King | Ace deriving (Show)
    type Card = (Rank, Suit)
    type Hand = [Card]
    
    value :: Rank -> Integer
    value Ten = 1
    value Jack = 2
    value Queen = 3
    value King = 4
    value Ace = 5

    cardValue :: Card -> Integer
    cardValue (rank, suit) = value rank
--
*Main> cardValue (Ten, Hearts)
1

多态函数

1
2
3
backwards :: [a] -> [a]
backwards [] = []
backwards (h:t) = backwards t ++ [h]

多态数据类型

类型相同的三元组
1
2
3
4
5
module Main where    
	data Triplet a = Trio a a a deriving (Show)
--
*Main> :t Trio
Trio :: a -> a -> a -> Triplet a
树
1
2
3
4
5
6
7
8
9
10
11
12
module Main where
    data Tree a = Children [Tree a] | Leaf a deriving (Show)
    
    -- 计算高度 --
    depth (Leaf _) = 1
    depth (Children c) = 1 + maximum (map depth c)
--
*Main> let leaf1 = Leaf 11
*Main> let leaf2 = Leaf 22
*Main> let tree = Children[Leaf 1, Leaf 2]
*Main> tree
Children [Leaf 1,Leaf 2]

类

非面向对象的类概念，它不涉及数据，可以精细控制重载和多态。

以下是 Eq 类的定义：

1
2
3
4
5
6
class  Eq a  where   
	(==), (/=) :: a -> a -> Bool
	-- Minimal complete definition:       
	--			(==) or (/=)   
	x /= y     =  not (x == y)   
	x == y     =  not (x /= y)

类支持继承：

Haskell Class Relation

Monad

海盗寻宝问题

Python Approach
1
2
3
4
5
def treasure_map(v):
    v = stagger(v)
    v = stagger(v)
    v = crawl(v)
    return v
Functional Approach
1
2
3
4
5
6
7
module Main where
	stagger :: (Num t) => t -> t
	stagger d = d + 2
	crawl d = d + 1
	
	treasureMap d =    
		crawl (stagger (stagger d))
Let-in Approach
1
2
3
4
5
6
module Main where
    letTreasureMap (v,d) = 
        let d1 = stagger d
            d2 = stagger d1
            d3 = crawl d2
        in d3
Monad Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
module Main where
    data Position t = Position t deriving (Show)
    stagger (Position d) = Position (d + 2)
    crawl (Position d) = Position (d + 2)

    rtn x = x			-- packaging monad
    x >>== f = f x	-- bind
    
    treasureMap pos = pos >>==
                      stagger >>==
                      stagger >>==
                      crawl >>==
                      rtn      
--
*Main> treasureMap (Position 0)
5

More Monad

do Sugar Syntax
1
2
3
4
5
6
module Main where
    tryIo = do 
        putStr "Enter your name: " ;
        line <- getLine ;
        let { backwards = reverse line} ;
        return ("Hello. Your backwards is " ++ backwards)
Definitions of return and bind(>>==)
1
2
3
instance Monad [] where
    m >>= f  = concatMap f m
    return x = [x]

Crack Password

1
2
3
4
5
6
7
8
9
module Main where
    crack = do 
        x <- ['a'..'c']; y <- ['a'..'c']; z <- ['a'..'c'];
        let {password = [x,y,z]};
        if attempt password
            then return (password, True)
            else return (password, False)

    attempt pw = if pw == "cab" then True else False

Maybe Monad

Maybe 能够解决一些函数返回失败，如数据库、网络、文件I/O等函数。

下面是 Just 定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{- Just 类似 Swift 的 Optional-}
Prelude> Just "some string"
Just "some string"
Prelude> Just Nothing
Just Nothing
Prelude> :t Just
Just :: a -> Maybe a
Prelude> :t Nothing
Nothing :: Maybe a

{- Def. of HTML handler -}
paragraph xmlDoc -> xmlDoc
body xmlDoc -> xmlDoc
html xmlDoc -> xmlDoc

进入正题，处理HTML文档，不用 Maybe Monad 时需要处理每层（paragraph / html / body）的 Nothing 异常：

1
2
3
4
5
6
7
8
9
{- Without Maybe Usage-}
paragraph body (html xmldoc)

{- Without Maybe Implementation (trival in handling exception)-}
case (html doc) of
	Nothing -> Nothing
	Just x  -> case body x of
		Nothing -> Nothing
		Just y  -> paragraph 2 y

用 Maybe Monad ：

1
2
3
4
5
6
7
8
9
{- Maybe Usage-}
Just someWebPage >>== html >>= body >>== paragraph >>== return

{- Def. of Maybe Monad -}
data Maybe a = Nothing | Just a
instance Monad Maybe where
    return         = Just
    Nothing  >>= f = Nothing
    (Just x) >>= f = f x
本文有帮助？