PHP实现Bitmap的探索 - GMP扩展使用

Category PHP
Tag PHP
Posted on
View

一、背景

公司当前有一个用户群的系统,核心功能是根据不同的条件组去不同的业务线中get符合条件的uid列表,然后存到redis中的bitmap中。

举个🌰,如果一个用户群中有两个用户: 3和7,即[3,7],用bitmap表示那就是:00010001

最后利用redis提供的bitOp命令: bitOp AND \ bitOp XOR \ bitOp OR对各个条件组对应的uid列表bitmap做交并差集计算,得出最终的用户群并存储到redis bitmap中。

二、问题

对于上面描述的系统,如果用户群人数较多的那我们就需要执行较多次的setBit {uid} 1命令,而且如果用户群中的第一个uid是一个特别大的值比如10亿的话,就可能会一次malloc 1000000000/1024/1024/8 ~= 120M的内存,这可能会导致redis卡住一段时间,在高并发的redis实例上执行这个操作是相当危险的。而且可以预想到对于两个较大的bitmap key执行bitOp也是非常消耗CPU的,应该尽量避免在存储型的redis实例中做这种十分消耗CPU的计算操作。

实际上内存最少只能申请一个字节,即8位,所以上面的计算方式稍有出入,但相差并不大。

三、解决方案

针对上述的问题,可以将bitmap的计算挪到应用程序中来,只将最终统计出来的bitmap存储到redis中即可。
如果最终结果用户群中的第一个uid是一个特别大的值的话,可以先set 1K再设置2K..3K…这样缓存的增加bitmap的大小避免redis卡住。

四、PHP实现Bitmap

由于该系统目前是使用的PHP,所以下面记录下PHP实现Bitmap的”心路历程“。

由于要操作PHP变量的某一位,所以就要借助位运算来实现,但是又由于PHP的位运算只能作用在整型数上,所以我们无法使用字符串或者浮点数来实现,所以最先考虑的就是使用整型数组来实现。

为什么是数组呢?因为在64位机器上一个整型变量最多只能使用64位,又由于PHP的整型是有符号的,所以最高位无法供我们使用,所以一个整型变量能存储的最大的uid就是63,这真是太鸡肋了-_-||,所以只能搞个用多个整型变量了实现了。

OK,到此为止貌似找到一个看起来不错的解决方案。但是我们再思考这样一个问题:假设我们系统中最大的uid是63x100万=3.6千万(*对主流互联网公司来说这很正常吧😸*),那为了存储所有uid,我们需要1百万个整数才行,即我们需要一个拥有1百万个元素的数组,那么如果我在进程中制造了一个这样的数组会占用多少内存呢?会是64 * 1百万 / 1024 / 1024 / 8 ~= 7.6M吗?答案是否定的,因为php数组是由HashTable实现的,这是一个复杂的结构体,除了数组元素占用的内存外,还有其他的占用。(这里先不做展开,有兴趣可以自行查看下php数组的实现) 眼见为实:

<?php
ini_set('memory_limit','4G');
$arr = [];
for ($i = 0; $i < 64 * 1000000; $i++)
{
    $arr[] = PHP_INT_MAX;
}

echo "done\n";
while(1){
}

查看内存占用

image.png

可以看到大概是1.5G,比我们上面预计的大的多,这太可怕了,必须优化下我们的内存占用,才能真正在生产环境中使用。

这里需要提一句,我的机器只有8G,所以程序可能会用到swap分区,而ps命令结果中的RSS不统计swap分区的占用,在我实际实现中发现ps结果中RSS一列显示占用的内存会随着时间慢慢减少,但是我的程序中arr变量占用的内存是不可能被回收的,所以推测是物理内存中占用的部分内存被置换到了swap分区中。如果你要进行这个实验的话建议关闭swap分区,这样你能得到一个更准确的结果。

五、继续优化

基于上面的经验,如果我们要占用尽可能小的内存,那我们必须能够操作一段近乎无限长的内存且不能产生其他额外占用才可以。幸运的是PHP给我们提供了这样一个扩展:GMP,这个扩展可以让我们使用一个任意长度的整数。OK现在我们拥有了获得一块连续的内存而不会产生其他额外占用的手段,再写一段代码使用下并验证下内存占用情况:

<?php

$gmp = gmp_init(0);
gmp_setbit($gmp, 64 * 1000000, true);
echo "done\n";
while(1){}

image.png

Awesome,这次只使用了15M的内存。更加兴奋的是这个扩展提供了诸如:gmp_andgmp_orgmp_xor这样进行位运算的函数,极大的方便了我们的使用。

到此为止我们似乎找到了一个完美的解决方案,但是真的完美吗?No!其实还可以再优化一下,想象下如果我们有一个用户群,里面只有一个uid:64000000(表示为数组的话就是:[64000000]),为了存储这个用户我们需要占用7.6M内存,而这个用户群中仅仅只有一个元素,这真是极大的浪费啊!

为了优化这个问题可以拥抱上面被我们唾弃的数组😸,一个大的bitmap拆分为一个个小bitmap的数组,这一个个小的bitmap我们限制大小为1Kw位。 image.png

回到上面的问题,如果我们要存储[64000000]这个用户群的话只需要在数组的第6个元素中设置一个little bitmap: 1即可。这样我们就由一开始的占用7.6M内存优化为了占用1位内存。

OK,到此为止我们找到一个还不错的解决方案😸。

后言

为了在Mac中安装GMP扩展又耗费了很多时间,当然,这又是另外一个故事了。有时间我会分享Mac中安装GMP扩展的过程中我遇到的问题。

参考资料

  1. GNU Multiple Precision
  2. Process Memory Management in Linux
  3. 从源码看 PHP 7 数组的实现

...

阅读全文 »

LR分析中shift/reduce reduce/reduce冲突解决方案SLR(1)与LR(1)

Category 编译器
Tag 编译器
Posted on
View

此篇文章要求读者对编译原理前端部分有一定了解 此篇文章中,我们以大写英文作为非终结符,小写英文作为终结符

1. LR(0)分析法简述

LR分析法从左至右移进输入的终结符(词法分析器的输出实际是token,但在语法分析阶段会代表是一个终结符),并将终结符压入到堆栈,称为shift。如果当前栈上的符号恰好符合某个非终结符的生成式,则此时进行归约操作:将这些符号弹出栈,然后将规约后的非终结符压入堆栈,这一步就称为reduce。然后继续上面的步骤,直到没有输入。
如果最终栈上只有一个非终结符,且该非终结符就是目标符号,那证明识别成功,否则识别失败。
名称LR得名于:从左(Left)到右扫描(L),反向(Reverse)最右推导(R)。

2. LR(0)分析法的不足

上面描述的算法存在一个问题,我们以下面的语法为例说明:

// 例1
B : A c
A : b d
  | b

对于上面的语法,当语法分析器遇到终结符b时,面临着两个选择,一个是继续移进下一个终结符,一个是使用生成式A : b进行归约。这种情况称为shift/reduce冲突
继续看下面一个例子:

// 例2
A : b
C : b
D : A a
E : C d

对于上面的语法,当语法分析器遇到终结符b时,面临着两个选择,一个是根据A : b,归约为A,另一个选择是使用生成式C : b进行归约。这种情况称为reduce/reduce冲突

因为这两种冲突的存在导致了LR(0)分析法在实际语法分析中基本不可用,必须找到解决这两种冲突的方案才行,那么如何这两种冲突呢?

3. SLR(1)

对于这两种冲突,我们首先先看一种简单的解决方案:SLR(1) (Simple LR)分析法。
SLR(1)分析法首先求出所有非终结符的Follow Set,即 跟在非终结符之后的所有终结符的集合,然后前瞻一个符号(即从词法分析器中预先读入下一个终结符),如果该前瞻符号在一个非终结符的Follow Set中,就根据此非终结符的生成式进行归约。

我们以上面的例2为例,SLR(1)分析器先求出A的Follow Set为{a},C的Follow Set为{b},假设当前输入为b a,输入b之后,语法分析器面临选择:归约到A or 归约到C,此时分析器前瞻一个符号即c,由于c属于A的Follow Set,所以分析器选择归约到A。

上面的例1也可以通过此算法解决shift/reduce冲突。

遗憾的是SLR(1)依然存在问题,这里举个例子就清楚了:

// 例3
T : S
S : aAd
S : bAc
S : aec
S : bed
A : e

首先求出各个非终结符的Follow Set:

Follow(T) = {}
Follow(S) = {}
Follow(A) = {d, c}

我们假设当前的输入为a e c, 当输入e时,SLR(1)分析器面临两个选择:继续移进下一个符号 or 根据A : e归约到A,此时SLR(1)分析器前瞻符号c,c存在于Follow(A)中,但此时又可以选择移进c,所以SLR(1)此时又面临着冲突了。

SLR(1)不足之处在于Follow Set太宽泛,处于Follow Set中的前瞻符号不一定能合法的跟在非终结符之后。实际上SLR(1)忽略了分析的上下文,针对SLR(1)的不足由提出了LR(1)分析法。

4. LR(1)

LR(1)的基本原理就是只要前瞻符号能合法跟在归约的非终结符之后就可以进行归约,LR(1)会为每个生成式绑定一个** LookAhead Set**,只有前瞻符号处于这个集合之中才进行归约,它是Follow Set的子集。那么LookAhead Set如何生成呢?

4.1 LookAhead Set生成

我们将生成式一般化为下面的样子:

s -> α .x β, C 
x -> . r

其中 s,x都是非终结符,α β r可以是终结符也可以是非终结符,C 为生成式的LookAhead Set。

x的LookAhead Set = First(β C),即β的FirstSet与C串起来之后的First集

First Set可以理解为非终结符所有生成式中第一个终结符的集合

5. Merak

我将LR(1)分析算法封装成了一个Golang Parser库:Merak,并且用它实现了一个面向对象语言的Parser: Mizar。对此有兴趣的同学可以试用下,它将为你省略手写语法分析器的过程,节省宝贵的时间投入到更加有趣的编译器后端工作中。

...

阅读全文 »

《我的第一个面向需求的Haskell程序》续

Category Haskell
Tag Haskell
Posted on
View

前言

上一篇《我的第一个面向需求的Haskell程序》文章中的Haskell程序还存在一个问题: 程序只打印出了文件中有没有重复的元素但是并没有告知是哪一个元素重复了,重复了几次也没有打印出来。 所以我继续优化下上篇文章中的Haskell程序,现在这段程序变成了下面这样

代码

module Main where

import Data.List.Split
import Data.List
import System.IO
import System.Environment

main = do
    args <- getArgs
    check args

check::[String] -> IO ()
check [filename] = do
    contents <- readFile filename
    mapM_ printRepeat $ fmap (\(x:xs) -> (x, 1 + length xs)) $ group $ splitOn "\r\n" contents
    putStrLn "check done"

check x = do
    putStrLn "请输入文件名"

printRepeat::(String, Int) -> IO()
printRepeat (word, num)
    | num > 1 = putStrLn $ word ++ " repeated " ++ (show num) ++ " times."
    | otherwise = return ()

使用

$ cabal build
$ ./dist-newstyle/build/x86_64-osx/ghc-8.8.4/repeat-0.1.0.0/x/repeat/build/repeat/repeat test.txt
joM2qWfjOJc repeated 2 times.
check done

解释

首先我们使用split包提供的splitOn 函数按照换行符将文件内容切分为[String],现在我们有了:

["abc", "abc", "def", "ghi", "def"]

然后使用group函数聚合下这个List,得到:

[["abc", "abc", "abc"], ["def", "def"], ["ghi"]]

再通过fmap (\(x:xs) -> (x, 1 + length xs))即map一个lambda表达式到这个List上,将这个List中的每个元素转为元组,得到:

[("abc", 3), ("def", 2), ("ghi", 1)]

至此我们实际做了一个WordCount程序…

接下来调用printRepeat函数打印出来结果就OK了

...

阅读全文 »

GNU 汇编器的语法

Category 汇编
Tag 编译器
Posted on
View

学习汇编语法的目的

为什么要学习汇编语法呢?原因是我最近在做一个面向对象语言的编译器(地址:https://github.com/Orlion/Mizar),目前已经完成了parser部分,即已经生成了AST,下一步要做的就是语义分析了,而语义分析之后要做的就是生成AT&T汇编代码了,所以有必要提前了解下汇编语法看在语义分析的实现阶段能否有所指导。

先看一段代码

首先我们有这样一段c语言代码:

#include <stdio.h>

char msg[14] = "Hello,world!\n";
 
int main(void)
{
    puts(msg);
    return 0;
}

运行 gcc -S -Os hello.c

    .file   "hello.c"
    .section    .text.startup,"ax",@progbits
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rax
    .cfi_def_cfa_offset 16
    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax
    popq    %rdx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .globl  msg
    .data
    .align 8
    .type   msg, @object
    .size   msg, 14
msg:
    .string "Hello,world!\n"
    .ident  "GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-39)"
    .section    .note.GNU-stack,"",@progbits

接下来解释下AT&T汇编的语法

指令

指令是直接由CPU负责处理的命令,不以.开头的行首缩进的行都是指令行。

    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax

指令由操作符和作为参数的操作数组成,以 movl $msg, %edi 为例,movl 为操作符, $msg%edi 为操作数,操作数以逗号来间隔。

汇编伪操作

. 开头末尾没有:的行都是汇编伪操作。例如,.file "hello.c", .globl main。汇编伪操作是由汇编器而非CPU处理的指令。一般用于在目标文件中记录元数据(meta data)或者设定指定的属性等。例如 .string 是用来定义字符串常量的汇编伪操作。

标签(labal)

以冒号: 结尾的行都是标签行,例如:.LFB0:,main:。 标签具有为汇编伪操作生成的数据或者指令命名(标上符号)的功能,这样就可以在其他地方调用通过标签定义的符号。 标签可以以.开头

注释

支持两种注释:

# xxx

/* xxx
xxx */

助记符后缀

刚才提到的movlsubl为助记符,更准确的说movsub为助记符,末尾的l是后缀,llong的缩写,表示操作对象的数据大小。类似这样的后缀还有b,w,l

|后缀|操作对象的大小|缩写| |-|-|-| |b|8位|byte| |w|16位|word| |l|32位|long|

操作数

操作数有四种: 1. 立即数 2. 寄存器 3. 直接内存引用 4. 间接内存引用

1. 立即数

立即数就是C语言中的字面量,机器语言中立即数以整数的形式出现,能高速访问。像$27这样,立即数用$来标识,如果漏掉了$就成了直接内存引用了。立即数有8位,16位,32位。

2. 寄存器

GUN汇编器规定寄存器以%开头,例如eax寄存器写作%eax

3. 直接内存引用

直接访问固定内存地址的方式。GNC汇编器会将任何整数解释为内存地址并访问。比起使用数字,更常用符号(symbol)直接访问内存。例如.LFE0就是访问符号.LFE0所指向的地址。符号在汇编和链接的过程中会被置换为实际内存地址。

4. 间接内存引用

是将寄存器的值作为内存地址访问的方式。间接内存引用中最通用的就是下方的形式:

disp(base, index, scale)

其中任何一者都可以省略。

上述指令访问disp + (base + index * scale)的地址。 下面详细讲解,首先最简单的间接引用的形式如下:

(%eax)

即只指定基地址(base)的形式。上述表达式将eax寄存器中的值作为内存地址访问。 接着带有disp的形式如下。disp是displacement(偏移)的简称。

4(%eax)

上述就是访问 4 + (eax寄存器中值) 这个内存地址。在C语言中用来访问如下结构体中成员y的情况:

struct point {
    int x; // x占4个字节,即4个内存地址
    int y;
}

最后使用index和scale的情况如下所示:

(%ebx, %eax, 4)

上面访问的就是(ebx寄存器中的值 + eax寄存器中的值 * 4)内存地址。在C语言中用来访问数组,例如访问元素大小为4字节(例如int)的数组中元素的第%ebx个元素时就可以用这种方式。当并非所有的数组访问都可以只靠间接内存引用来表示,因为scale只能是1、2、4、8之一。

2020-09-22更

突然意识到如果要将一个复杂工程的AST编译为汇编代码必须具备能够用汇编实现这个复杂工程的能力才行,这太难了… 所以暂时放弃吧,先编译到了LLVM IR再说,嗯。

2020-10-07更

不如趁此机会学习下汇编以及后续的链接装载,有助于建立宏观的了解。所以还是继续学习吧。 😸

未完待续…

...

阅读全文 »

对Haskell惰性求值的理解

Category Haskell
Tag Haskell
Posted on
View

全文均为伪代码,没有验证,只可意会

doIf::Bool -> a -> Maybe a
doIf cond action = if cond then (Maybe action) else Nothing

我们声明了一个doIf函数,它接收两个参数:cond与action,它干一件事:如果cond == true 就调用action,并包在Maybe中返回。 如果是strict的语言的话,在调用doIf函数的之时action就会被执行了,而Haskell默认是non-strict的,所以在调用doIf时,action无需求值,只有在cond为true时才需要对action求值,如果cond为false的话action根本不会被执行,这就是non-strict与strict的区别。

...

阅读全文 »

我的第一个面向需求的Haskell程序

Category Haskell
Tag Haskell
Tag cabal
Posted on
View

背景

上周五(20年8月28日)的时候,公司测试同学需要测试我的一个提测需求,其中有个测试用例是需要检查下下后台导出的兑换口令列表文件中是否有重复的口令。

由于导出的口令有数百万之多,肯定是不能用眼去看了,原本是打算用excel来检查的,但是我一想:ei(二声)~,最近不是正好在搞Haskell吗?正好拿来练练手,用Haskell写个检测程序。

Why is Haskell

因为这个程序写出来是要交给测试同学使用的,如果用java或者php这种解释型语言来写,还需要测试同学先去安装个java/php的解释器才行,显然是有点扯的,所以用编译型语言写完后直接build出一个可执行文件才比较方便。

当然可以将java/php的程序打包成一个可执行文件,但是又要花费我一些不必要的时间了。

编译型语言中我常用的有golang和Haskell。不可否认Go面对这个需求写起来可能更快,但是我其实还是想用Haskell练练手。

那? 开始吧!

首先,使用cabal创建一个项目

$ mkdir repeat && cd repeat
$ cabal init

导出的口令文件是以\r\n换行的,haskell的lines函数无法切分,所以需要通过cabal引入一个包:split,我的repeat.cabal文件就变成了下面这样了:

cabal-version:       >=1.10
-- Initial package description 'repeat.cabal' generated by 'cabal init'.
-- For further documentation, see http://haskell.org/cabal/users-guide/

name:                repeat
version:             0.1.0.0
-- synopsis:
-- description:
-- bug-reports:
-- license:
license-file:        LICENSE
author:              wangdongdong
maintainer:          wangdongdong@smzdm.com
-- copyright:
-- category:
build-type:          Simple
extra-source-files:  CHANGELOG.md

executable repeat
  main-is:             Main.hs
  -- other-modules:
  -- other-extensions:
  build-depends:       base >=4.13 && <4.14, split
  -- hs-source-dirs:
  default-language:    Haskell2010

编辑Main.hs

module Main where

import Data.List.Split
import Data.List
import System.IO
import System.Environment

main = do
    args <- getArgs
    check args

-- 通过模式匹配获取命令行参数中的文件名
check::[String] -> IO ()
check [filename] = do
    contents <- readFile filename
    -- 暴力通过去重后的list length对比来判重,不可取
    if (length $ mylines contents) /= (length $ nub $ mylines contents)
        then putStrLn "有重复元素" 
        else putStrLn "没有重复元素"

check x = putStrLn "请输入文件名"

-- 通过split库的splitOn函数以\r\n为切割符将文件内容切分为list
mylines contents = splitOn "\r\n" contents

最后编译为可执行文件

$ cabal build

编译结果在dist-newstype文件夹之中

交付使用

$ ./repeat keywords.txt

能够满足需求!

后续优化请看

《我的第一个面向需求的Haskell程序》续

...

阅读全文 »

go mod 提示 unknown revision问题

Category Golang
Tag Go
Tag git
Posted on
View

通过go mod download下载公司gitlab仓库代码时提示unknown revision 由于是私有仓库且回车执行命令后并没有输入密码的提示,所以猜测是go mod download时git clone 没有输入密码提示

一番搜索后发现解决方案如下:

// 设置永久存储账号密码
git config credential.helper store
// git pull过程中允许输入用户名密码
export GIT_TERMINAL_PROMPT=1

...

阅读全文 »

golang 中的一些tips [持续更新中]

Category Golang
Tag Go
Posted on
View

new() 函数

golang中的new是一个用户分配内存的函数,new(T) 为类型T分配一块内存,初始化为T类型的零值,并返回它的地址,即类型为*T的指针

int的零值是0,bool的零值是false,结构体的零值是其各元素零值的一个对象,

 type Person struct {
	Name string
	Age int
 }

的零值就是Person{“”, 0}

以Person结构体为例,new(Person) 实际等价于 &Person{}

struct 值方法与指针方法

type Person struct {
	Name string
}

// 值方法
func (p Person) SetName1(name string) {
	p.Name = name
}
// 指针方法
func (p *Person) SetName2(name string) {
	p.Name = name
}

结构体方法可以想象为:(这里并不严格)

func SetName1(p Person, name string) { ... }
func SetName2(p *Person, name string) { ... }

这样就一目了然了,一个是值传递,一个是指针传递。

还有一点需要注意:

p1 := Person{}
p2 := &Person{}

p1.SetName2("p1") // 实际会被当为 (&p1).SetName2()
p2.SetName1("p2") // 实际会被当为 (*p2).SetName1()

fmt.Println(p1.Name) // 输出p1
fmt.Println(p2.Name) // 输出空字符串

面对interface时的一个tip

如果有这样一个接口:

type Animal interface{
	SetName()
	SetAge()
}
type Cat struct {
	
}

func (cat Cat) SetName() {}
func (cat *Cat) SetAge() {}

func foo(a Animal) {
	a.SetName()
}

c1 := Cat{}
c2 := &Cat{}

foo(c1) // 报错:cat这个类型没有实现Animal接口的SetAge方法
foo(c2) // 通过

通过上面的例子可以看到: 一个指针类型拥有以它以及以它的基底类型为接收者类型的所有方法,而它的基底类型却至拥有以它本身为接收者类型的方法

变量作用域问题

有下面这个程序,猜下会怎样输出呢?

foo := 1
if true {
	foo := 2
	fmt.Println(foo)
}

fmt.Println(foo)

以为会输出2 2 ? 错!实际输出2 1

原因是go 的语义块中定义的变量是该语句块中的局部变量,if语句块中的foo实际通过 := 声明赋值时,决定了这个foo只是当前if语句块中的foo,而不是外部的foo

...

阅读全文 »

haskell 中的newtype

Category Haskell
Tag Haskell
Posted on
View

haskell中一般使用data关键字来自定义type,像这样:

data BookInfo = Book Int String [String] deriving (Show)

但有些情况下要使用newtype来定义, 举个例子,对于数字来说,它有两种选择可以表现为一个monoid,一个是 * 作为二元函数,1 作为identity, 另外一种是 + 作为二元函数,0 作为identity。那么问题来了怎么把这两种选择都实现 (这里所说的实现是指把一个数字实现为Monoid这个typeclass的instance) 呢?

Data.Monoid 这个模块导出了两个类型:ProductSum 。Product的定义如下:

Prelude Data.Monoid> :i Product
newtype Product a = Product {getProduct :: a}

Sum的定义如下:

Prelude Data.Monoid> :i Sum
newtype Sum a = Sum {getSum :: a}

Product的Monoid的instance实现:

instance Num a => Monoid (Product a) where  
    mempty = Product 1  
    Product x `mappend` Product y = Product (x * y)

很显然它将第一种选择即乘法实现了。它代表 Product a 对于所有属于 Numa 是一个 Monoid

为什么要用newtype呢?

因为newtype比较快。 如果用data的话在执行的时候会有包起来和解开来的成本,但使用newtype的话,Haskell会知道你只是要将一个type包成一个新的type,你想要内部运作完全一样只是要一个新type而已。有了这个概念,Haskell可以将包裹和解开的成本省掉。

为什么不能所有地方都用newtype呢,是因为当使用newtype来制作一个新type的时候,只能有一个值构造器,而且这个值构造器只能有一个字段。

...

阅读全文 »

一些范畴论上的概念

Category Haskell
Tag Haskell
Posted on
View

为了能真正理解Haskell中的Functor、Applicative、Monad、Monoid,以及它们到底有什么用,个人觉得还是有必要 了解 一些范畴论里面的概念的

函数 Function

函数表示特定类型之间的 态射

自函数 EndoFunction

自函数就是把类型映射到自身类型

identity :: Number -> Number

identity函数就是一个自函数的例子,它接收什么就返回什么

函子 Functor

函子与函数不同,函数描述的是类型之间的映射,而函子描述的是 范畴(category) 之间的映射

范畴

范畴是一组类型及其关系 态射 的集合。包括特定类型及其态射,比如: Int、 String、 Int -> String ;高阶类型及其态射,比如 List[Int]、 List[String]、 List[Int] -> List[String]

函子如何映射两个范畴

image.png

图中,范畴C1和范畴c2之间有映射关系,C1中Int映射到C2List[Int],C1中String映射到C2List[String],C1中的关系态射Int -> String 也映射到 C2中的关系List[Int] -> List[String]态射上。

也就是说,一个范畴内部的所有元素可以映射为另一个范畴的元素,且元素间的关系也可以映射为另一范畴中的元素间的关系,则设为这两个范畴之间存在映射。所谓函子就是表示两个范畴之间的映射。

Haskell中,Functor是可以被map over的东西,List就是一个典型的instance。构造List[Int] 就是把Int提升到List[Int],记作:Int -> List[Int] . 这表达了一个范畴的元素可以被映射为另一个范畴的元素

我们看下Haskell中map函数的定义:

map :: (a -> b) -> [a] -> [b]

把我们上面的Int String的例子代入,配合柯里化的概念可以得出:

map :: (Int -> String) -> (List[Int] -> List[String])

map的定义清晰的告诉我们: Int -> String 这个关系可以被映射为 List[Int] -> List[String] 这种关系。这就表达了元素间的关系可以映射为另外一个范畴元素间的关系

所以List就是一个Functor

自函子

自函数是把类型映射到自身类型,那么自函子就是把范畴映射到自身范畴。

image.png

上图就是一个将范畴映射到自身的自函子。从函子的定义出发,我们考察这个自函子,始终有List[Int] -> List[String]List[Int] -> List[String] -> List[Int] -> List[String] 这两种映射。我们表述为:

类型List[Int] 映射到自己
态射f :: List[Int] -> List[String] 映射到自己

我们记作:

F(List[Int]) = List[Int]
F(f) = f
其中F是Functor

幺半群

先解释下群的概念:G为非空集合,如果在G上定义的二元运算*,满足:

(1) 封闭性:(Closure):对于任意a,b∈G,有a*b∈G
(2) 结合律(Associativity):对于任意a,b,c∈G,有(a*b)*c=a*(b*c)
(3) 幺元 (Identity):存在幺元e,使得对于任意a∈G,e*a=a*e=a
(4) 逆元:对于任意a∈G,存在逆元a^-1,使得a^-1*a=a*a^-1=e

则称(G, *) 为群,简称G为群。

如果仅满足封闭性和结合律,则该G是一个 半群(Semigroup) ; 如果满足封闭性和结合律并且存在幺元,则该G是一个 幺半群(Monoid)

接下来看下在自函子的范畴上,怎样结合幺半群的定义得出Monad

假设我们有个cube函数,它计算一个数的三次方:

cube :: Number -> Number

现在我们想在其返回值上添加一些调试信息,返回一个元组,第二个元素代表调试信息,函数签名为:

f :: Number -> (Number, String)

可以看到参数与返回值不一致。我们再看下幺半群规定的结合律。对于函数而言,结合律就是将函数以各种结合方式嵌套起来调用。我们将Haskell中的 . 函数看做这里的二元运算。

(.) :: (b -> c) -> (a -> b) -> a -> c

f . f

从函数签名可以看出右边f返回的是元组(Number, String),而左侧的f接收的是Number。所以无法组合,他们彼此不兼容。

有什么办法能消除这种不兼容?结合前面所述,cube是一个自函数,元组(Number,String)在Hask范畴是一个自函子 (这个说法看起来并不准确,(?, String)才应该是一个自函子 ) , 理由如下:

F Number = (Number, String)
F Number -> Number = (Number,String) -> (Number,String)

如果输入和输出都是元组,结果会怎样呢?

fn :: (Number,String) -> (Number,String)
fn . fn

这样是可行的,在验证满足结合律之前,我们引入一个liftM函数来辅助将f提升成fn

liftM :: (Double -> (Double, String)) -> (Double,String) -> (Double, String)
liftM f (x,y) = case r of (n,s) -> (n, y ++ s)
    where r = f x 

没有验证,就当伪代码看吧

我们来实现元组自函子范畴上的结合律:

cube :: Number -> (Number, String)
cube x = (x * x * x, "cube was called.")

sine :: Number -> (Number, String)
sine x = (Math.sin x, "sine was called.")

f = ((liftM sine) . (liftM cube)) . (liftM cube)
f (3, "")
输出:(0.956, 'cube was called.cube was called.sine was called.')

f1 = (liftM sine) . ((liftM cube) . (liftM cube))
输出:(0.956, 'cube was called.cube was called.sine was called.')

这里f和f1代表的结合顺序产生了相同的结果,说明元组自函子范畴满足结合律。

那如何找到这样一个e,使得 a * e = e * a = a ,此处的 * 就是 .

unit :: Number -> (Number, String)
unit x = (x, "")

f = (liftM sine) . (liftM cube)

f . (liftM unit) = (liftM unit) . f = f

这里的 liftM unit 就是 e 了。

unit 个人理解应该就是类型构造器

...

阅读全文 »