logN's blog

2016-02-09
haskell之自定义类型

自定义类型

关键字data

花括号{}自动生成访问成员函数

1
data Person = Person{ name :: String
                    , age :: Int
                    , weight :: Float
                    } deriving (Show)
let x = Person "hanhan" 27 90
weight x

这里我们也看出了函数式OOP一个关于访问成员对象的很分明的区别。

定义好名字,构造时可不关心参数顺序

1
2
data Point  = Point { x :: Int, y :: Int } deriving (Show)
let y = Point { y = 2, x = 1}

常用deriving

1
deriving (Eq, Ord, Show, Read, Bounded, Enum)

Type parameters

Maybe类型定义

1
data Maybe a = Nothing | Just a

个人感觉有haskellMaybe点像c++里面的泛型,并且它允许Nothing,而Nothing的类型为Maybe a.
[Type parameters]待补充

阅读此文

2016-02-09
haskell中的查找二叉树及其三大二叉树遍历

递归方式定义二叉树

1
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

对照着c++代码来看就很容易懂这里定义的对应的是什么

1
2
3
4
struct Tree {
a val;
Tree *left, *right;
};

插入函数

这里用一个简单的模式匹配就能搞定

1
2
3
4
5
6
insertTree :: (Ord a) => a -> Tree a -> Tree a
insertTree x EmptyTree = Node x EmptyTree EmptyTree
insertTree x (Node a left right)
| x == a = Node x left right
| x < a = Node a (insertTree x left) right
| x > a = Node a left (insertTree x right)

查询函数

1
2
3
4
5
6
findElement :: (Ord a) => a -> Tree a -> Bool
findElement x EmptyTree = False
findElement x (Node a left right)
| x == a = True
| x < a = findElement x left
| x > a = findElement x right

遍历

后序遍历

1
2
3
postOrder :: (Ord a) => Tree a -> [a]
postOrder EmptyTree = []
postOrder (Node a left right) = (postOrder left) ++ (postOrder right) ++ [a]

如法炮制中序遍历

1
2
3
inOrder :: (Ord a) => Tree a -> [a]
inOrder EmptyTree = []
inOrder (Node a left right) = (inOrder left) ++ [a] ++ (inOrder right)

先序遍历什么的还难么= =

测试

1
let e = [1,2,3,4,-1,9,12,3,-10]
let t = foldr insertTree EmptyTree e
postOrder t
输出:[1,2,-1,4,9,12,3,-10]
inOrder t
输出: [-10,-1,1,2,3,4,9,12]
阅读此文

2016-02-08
haskell的module

解决冲突

比如Data.SetDatal.List两个模块存在命名冲突,我们可以为模块重命名

1
import qualified Data.Set as Set

建立自己的module

单文件module例子

在同一目录下
module文件:
MyModule.hs

1
2
3
4
5
6
7
8
9
10
module MyModule
( getDistance
, doubleInt
) where


getDistance :: (RealFloat a) => a->a->a
getDistance a b = sqrt(a * a + b * b)

doubleInt :: (Integral a) => a -> a
doubleInt a = a + a

main函数文件:

1
2
3
4
import MyModule
main = do
print(doubleInt 2)
print(getDistance 1 1)

用目录组织module例子

目录结构

1
module_dir/
├── Test
│   └── add.hs
└── main.hs

main.hs:

1
2
3
import Test.Add
main =
print(add2 2)

add.hs:

1
2
3
4
5
6
7
8
9
10
module Test.Add
(add2
,add3
)where


add2::Int->Int
add2 x = x + 2

add3::Int->Int
add3 x = x + 3

阅读此文

2016-02-04
haskell高阶函数学习

高阶函数定义

至少满足其一:

  1. 函数本身返回一个函数
  2. 接受一个以上函数作为输入

柯里化

高阶函数一般会涉及到柯里化,柯里化在wiki的定义是指把接受多个参数的函数变换成接受单一参数的函数,并且返回接受余下参数而且返回结果的新函数的技术。

例子

高阶函数比较常见的有map,filter之类的。
比如map的代码定义为

1
(define (map op seq))

map接受一个op作为操作seq中每一个元素的函数。

在haskell中,我们定义一个apply3函数

1
2
apply3 :: (a->a)->a->a
apply3 f x = f (f (f x))

然后给这个apply3函数传入一个(+3)一元函数和参数3

1
apply3 (+3) 10

得到结果19

再比如标准函数flip用于交换函数处理顺序能写成

1
2
flip' :: (a -> b -> c) -> b -> a -> c  
flip' f y x = f x y

试试这个flip'函数

1
2
3
let test2 x y = x * 2 + y
flip' test2 1 2
test2 1 2

这两个结果分别是54

再用haskell来实现一个map

1
2
3
map' :: (a->b)->[a]->[b]
map' f xs = case xs of [] -> []
(x:_) -> (f x):(map' f (tail xs))

在我的看来,高阶函数一个好处是能存储函数的状态,可以做类似lazy evaluation的工作,把一些复杂的计算或者耗时的操作放在恰当的时间来做。

$函数

用来改变优先级的
比如

1
sum (map (+1) [1, 2, 3])

可以写作

1
sum $ map (+1) [1, 2, 3]

可以省略几个括号。
此外还可以用来 map数据
一般我们都是map operation list这样的格式
因为这个$是一个函数,我们可以改写为map ($ number) [list of operation]
比如

1
map ($ 2) [(+2), (/ 3), sqrt]

点组合函数

.是一个点组合函数,向右结合,比如

1
2
3

map ((+2).(*3)) [1,2,3]
map ((*3).(+2)) [1,2,3]

这两个结果是不一样的

PointFree风格

用来省略实际的参数风格
比如:

1
let s xs = foldr (+) 0 xs

这个函数两边都有xs,我们省略写为

1
let s1 = foldr (+) 0

再如

1
let add2 x = x + 2
let mul3 x = x * 3

let f x = add2 (mul3 x)

最后一句x两边都出现了,可以简写为

1
let f = add2 . mul3

阅读此文

2016-02-03
haskell速查

haskell在断断续续的学习,只是老停留在语法阶段,从scala学习一段时间再看haskell发现一些概念也比较清楚了。下面是一些用于速查的东西。

ghci速查

:t TYPENAME 显示类型
:load filename 在ghci下加载一个hs文件
:reload 重新加载已经加载的文件

常数函数

takeWhile 一般用于遍历list截止条件

1
takeWhile (< 100) (filter odd [1..])

基本类型

Int
IntegerInt精度要高
例子:

1
2
3
4
fac' :: (Integral a) => a->a
fac' 0 = 1
fac' 1 = 1
fac' n = n * fac'(n - 1)

Float
Double
Bool
Char

Typeclasses

Eq
ShowRead作用相反
Read单独使用要给他回传值

1
2
read "4" + 4
read "4" :: Int

Read可以直接读List

1
read "[1,2,3,4]"::[Int]

Bounded

1
2
minBound::Int
maxBound::Int

Guard

比较像haskell的if语句

1
2
3
4
plusTen :: (Integral a) => a->a
plusTen f
| f <= 50 = f + 10
| otherwise = f

where

一般和Guard连用,一般绑定在函数尾部

1
2
3
4
5
6
7
8
9
getGrade :: (Integral a) => a -> String
getGrade g
| g > great = "Great"
| g > good = "Good"
| g > notBad = "NotBad"
| otherwise = "Failed"
where great = 90
good = 80
notBad = 60

let

一般格式为 let [绑定参数] in [表达式]
in确定了绑定参数的有效区
例子

1
2
3
4
5
getDistance :: (RealFloat a) => a->a->a
getDistance a b =
let a' = a * a
b' = b * b
in sqrt(a' + b')

可以看出let一般是用来绑定表达式
用于局部绑定

1
1 + (let a = 5 in a + 1) * 4

定义一个函数

1
let add3 a b c = a + b + c

这个时候in可以省略

case

case有点坑,和python一样有强迫症,需要注意condition的对齐

1
2
3
head' :: [a] -> a  
head' xs = case xs of [] -> error "No head for empty lists!"
(x:_) -> x
阅读此文

2016-02-02
bash中的emacs和vi模式

火星了,虽然不是emacs党,但是现在才知道命令行的跳转快捷键都是emacs风格的。
在bash中直接输入

1
2
set -o vi
set -o emacs

即可切换命令行的模式,如果熟悉vi的话会比较爽的。
一般默认的是emacs模式,所以快捷键查阅起来感觉有点诡异。
我现在关于bash的命令跳转键还算够用,比如最多的还是ctrl+a,ctrl+e这种简单的跳转。实在不行到觉得很麻烦就上vi模式吧= =。

阅读此文

2016-02-01
map和flatmap

首先看看SICP上的关于map和flatmap的代码

map:

1
2
3
4
5
(define (map op items)
(if (null? )
null
(cons (op (car items))
(map op (cdr items))))
)

flatmap:

1
2
3
4
5
6
7
8
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence))))
)


(define (flatmap proc seq)
(accumulate append empty (map proc seq)))

我们可以看出flatmap是map和accumulate的组合,而且由于append的关系,map对seq操作必须返回一个list,所以flatmap可以理解为对seq的每一个元素映射为List类型,然后用append操作把所有的List“拉直铺平”,所以这个操作命名为flat(平)map。

看看scala的例子
例子:

1
2
3
4
5
6
7
object flatmap {
def main(args: Array[String]): Unit = {
val l : List[Int] = List(1, 2, 3)
println(l.flatMap(a => List(a + 1, a + 2)))
println(l.map(a => List(a + 1, a + 2)))
}
}

结果为

1
List(2, 3, 3, 4, 4, 5)
List(List(2, 3), List(3, 4), List(4, 5))

这个“flat”操作把本应该为list的结果“拉直”了。

阅读此文