haskell 中可描述的对象

  • 类型构造子：含有kind属性，用于构造函数的类型签名。任意一个值构造子/函数（无论是几个参数的）的type都是被full applied的，所以这个 type 所对应的kind都是*
  • 值构造子：含有type属性。
  • 函数也可认为是通过模式匹配 来组合使用多个 值构造子的特殊的值构造子，所以函数也有type属性。作为函数/值构造子的参数
  • 值等价于函数，传统的值就是一个无参函数

函数与容器?

另外 Maybe、[] 与 (->) r 都是 Functor 的实例，一定程度上表明了它们的联系。基于下面的的描述，可把Functor作为一种容器

容器可以理解为函数

函数(->) a Int的一个值 \_ -> 1

1
2
3
unMaybe m = case m of 
	Just a -> a
	Nothing -> undefined

容器Maybe Int 的一个值 Just 1，它也可理解为\_ -> unMaybe(Just 1)类型是(->) () Int

所以说Maybe Int可理解为(->) a Int

所以Maybe与(->) a本质上是类似的，只不过Maybe表达的是忽略参数的函数，并且通过模式匹配来实现了这个虚拟函数的调用(从而取出容器内的值)

函数也可以理解为容器

函数可以看作特殊的容器类型(->) r，通过传入一个参数（类型是r）来取出容器中的值。

普通的容器，如Maybe、[]用模式匹配来取出值。

并且他们的kind是相同的:k Maybe == * -> *，:k ((->) Int) == * -> *，因此 (->) a Int 类似于 Maybe Int，而(->) a ((->) a Int) 类似于 Maybe (Maybe Int)

进一步的，如果把(->) Int 命名一个别名为Func(type Func = (->) Int)，那么Func Int 类似于 Maybe Int ，Func (Func Int) 类似于 Maybe (Maybe Int)

kind

  • 每个typeConstructor都有自己的kind，就像每个valueConstructor（也就是function，在这里包含无参的function）都有自己的type
  • 一个typeConstructor的某个valueConstructor的type的形式与这个typeConstructor的kind的形式上一致
1
2
:t Nothing 与 :k Maybe Int 形式一致
:t Just 与 :k Maybe 形式一致

通过:kind <type>或者:k <type>查看typeConstructor的kind

1
2
3
-- <type>引用的是type/data
<kindDesc> ::= (*|<type>) [ -> (*|<type>)]*
<kindAnno> ::= <type> :: <kindDesc>
  • *：代表是具体type，对应的值是无参的
  • * -> *：代表一个单参数typeConstructor，需要传递一个无参typeConstructor，然后会返回一个无参typeConstructor。这个type对应的值(即function)是1参的
  • * -> * -> *，等价于* -> (* -> *)，代表一个二参数typeConstructor。这个type对应的值(即function)是2参的
  • (* -> *) -> *：代表传递一个单参数typeConstructor，返回一个无参typeConstructor。这个type对应的值(即function)是1参的
  • 以此类推，可以加很多层->

类型描述/类型注释

  • 类型描述

  • :type <exp>和:t <exp>查看值的类型

1
2
3
4
5
6
7
-- <type> 引用的是type/data，<typeVar> 引用的是typeclass
-- ->是右结合的(infixr 0)，即a->b->c->d == (a->(b->(c->d))) != (((a->b)->c)->d)

-- <typeDesc> ::= [<constrains> =>] [<full applied type> -> ]* <full applied type> ，或者说直接下面这样（因为`->`是类型构造子）
<typeDesc> ::= [<constrains> =>] <type> 
<constrains> ::= <constrain> | (<constrain> (, <constrain>)+)
<constrain> ::= <typeclass> <typeVar>+
  • 类型注释

代表这些<exp>的结果都是<typeDesc>所描述的类型

1
<typeAnno> ::= <exp> (, <exp>)* :: <typeDesc>

Type（algebraic data type）

  • type：代表有参或无参的typeConstructor
1
2
3
4
5
6
7
8

-- [a]是[] a的语法糖，同样[1,2]是1:2:[]的语法糖，不过`:`是右结合的
data [] a = [] | a : [a]

-- 定义自己的list
data XList a = XEmptyList | XInsertHead a (XList a) deriving(Show,Read)
-- 或者
data XList a = XEmptyList |  a `XInsertHead` (XList a) deriving(Show,Read) -- `XInsertHead`是左结合的

data

创建一个新的typeConstructor以及一些valueConstructor(不是必须的)，但是用的是data关键字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
data <typeDef> [ = <value> (|<value>)* deriving (<typeClass> (, <typeClass>)*) ]

<typeDef> ::= <typeConstructor> (<typeArg> <kindConstrain>)* 

-- 类型参数，并非实际的类型引用。在定义时不能为这个类型添加约束，Haskell要求在函数定义中加入需要的约束，而不是在类型定义中
<typeArg> := [a-z].*

-- 这里的<typeArg>必须是<typeDef>中包含了的，无参数的值构造子称作nullary的。`<valueConstructor>`可以是中缀的
<value> ::= <valueConstructor> (<type>|<typeArg>)* | (<type|<typeArg>) 中缀的<valueConstructor> (<type>|<typeArg>)

<type> ::= <typeArg> | <typeConstructor> <type>* -- <type> 这里是引用的自身，<typeArg>是上下文中含有的类型参数。==typeConstructor同样可以部分传递参数，所以可以把具体type理解为一个无参的typeConstructor==

-- typeConstructor和valueConstructor可以一样，因为两者的使用位置不同，一个用来表达类型，一个用于表达函数
<typeConstructor> | <valueConstructor> ::= [A-Z].*
  • 像这样定义了一个type后，可以通过<typeConstructor>构造一个类型。XList Int、Map Int（类型参数也可以部分指定，可以用于简化类型别名的定义）
  • typeConstructor只能前缀部分调用，不能中缀部分调用，中缀全调用是可以的
  • <valueConstructor>就是一个函数（不是普通的函数，普通的函数名开头是小写的，所以不能通过定义普通函数来创建），这个函数的参数类型就是<type>*决定的，调用这个函数会返回一个<type>类型的值，并且会根据类型推断添加类型参数的类型约束data D a = D1 a; D1 1 :: Num a => D a
  • ==模式匹配实际就是匹配的<value>==，通过指定<valueConstructor>以及<constructorArg>就能匹配到<constructorArg>的值
1
data [] a = [] | a : [a]
  • 如[]类型构造子拥有一个参数a，这个参数指定了元素的类型，它有两个值构造子[]（无参）、:（两个参数，类型是a和[a]）。
  • 而匹配的时候[]匹配了第一个值构造子，a:b:c匹配了第二个值构造子两次

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)
-----------------------
data Point = Point Float Float deriving (Show)

-- 展示如何在type定义中使用其它type
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

surface :: Shape -> Float
surface (Circle _ r) = pi * r ^ 2
-- 使用值构造子匹配值
surface (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 - x1) * (abs $ y2 - y1)

-- 展示如何使用值构造子创建值
surface (Rectangle (Point 0 0) (Point 100 100))
Record Syntax

为值构造子的参数设置名字的语法。

1
2
3
4
5
6
7
-- 这里的这个<value>与type/data的<value>对应，<type>也是（这里的type必须是无参typeConstructor）
<value> ::= <valueConstructor> { <arg> (, <arg>)* }
<arg> ::= <argName> :: <type>

-- 展示如何使用值构造子创建值
<valueConstructor> { <value'> (, <value'>)* }
<value'> ::= <argName> = <val>

实例：

1
2
3
4
5
6
7
-- 生成了三个函数：company :: Car -> String。。。
data Car = Car {company :: String, model :: String, year :: Int} deriving (Show)
-- 构造值
Car {company="Ford", model="Mustang", year=1967}
-- 匹配值
f Car {company=a, model=b, year=c} = a ++ b ++ (show c)
f Car {company="c", model="m", year=1} -- cm1
  • 实际会生成一系列利用了模式匹配的单参数函数(company :: Car -> String)，参数就是该类型的值，返回值就是函数名对应的<argName>值
类型参数 <typeArg> / 类型变量 <typeVar>

类型参数是需要被传递的参数（可传递type，包括可传递上下文中已有的类型变量），存在于类型定义(<typeDef>)中。

类型变量是用来指代某个被约束的类型范围，是个占位符，能够进行推断，或者通过::手动指定。本身就是代表某个type，可以像type（Int、[Char]、Maybe(partial applied)）一样使用。

1
2
-- Maybe类型的定义
data Maybe a = Nothing | Just a

对于那些含有<typeArg>的定义，如<type>。

构造一个type可以通过传递上下文中已存在的”类型变量”，如Just 1 :: (Num a) => a -> Maybe a中，把已有的类型变量a传递给了Maybe这个<typeConstructor>，函数调用时类型变量a的类型总是可以确定；也可以通过传递具体的<type>，如createIntMaybe :: Int -> Maybe Int中的Maybe Int，来代表一个<type>。

  • Map Int（类型参数也可以部分指定，可用于类型的定义）
    1
    2
    3
    type IntMap v = Map Int v
-- 类似函数的point free style
type IntMap  = Map Int
deriving

类似于实现接口

  • 只能 deriving typeclass，deriving会由编译器自动进行instance的添加

Eq、Ord、Enum、Bounded、Show、Read这些typeClass如何deriving：

1
2
3
4
5
6
7
8
9
data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int
                     } deriving (Eq, Show, Read)
show Person {firstName = "Michael", lastName = "Diamond", age = 43}
Person {firstName = \"Michael\", lastName = \"Diamond\", age = 43}"

read Person {firstName = \"Michael\", lastName = \"Diamond\", age = 43}" :: Person
Person {firstName = "Michael", lastName = "Diamond", age = 43}
  • Eq，只要==或/=比较时左右两边是相同的值构造子，就会通过比较各个值是否相等来作为比较结果，所以各个值的type也是需要是Eq的instance。如果是同一type的不同值构造子构造的值那么会返回False
  • Show或Read：只要各个值的type都是Show或Read的instance就行
  • Ord，值构造子的各个值的type也必须是Ord的instance，比较双方必须是同一type（(<) :: a -> a -> Bool），如果是不同的值构造子(左边的小于右边的，Nothing < Just 1)，如果是相同的值构造子（依次比较值的大小）
  • Bounded，与Ord一样，能够比较大小，但是要求能有最大最小值并且值构造子都是nullary的。minBound :: a、maxBound :: a，这两个函数是无参函数，但是仍然能够指定”类型变量”的具体类型，来获取该类型的最大最小值（minBound :: Int）。
  • Enum，每个元素有前驱和后继（之构造值的前后，并且值构造子必须都是nullary的），可枚举的类型能够通过..的方式获取一个值的列表，如[1,2..10]

newtype

  • newtype必须有且只能有一个值构造子，并且这个值构造子也必须有且只能有一个参数
  • 在编译期，这个值构造子是存在的，但是在运行期是不存在的
  • 而普通的data，在编译期值构造子肯定也是存在的，在运行期也是不存在的，但是它会生成一个Dictionary用来记录某个值是由哪个值构造子创建的。而newtype创建的值构造子就不会，为的就是节省这个开销，在例子中就相当于Nt直接使用了D的值构造子，因为没有必要再加一层了
1
2
data D = Dc Int Int deriving(Show)
newtype Nt = Nc D deriving(Show)
  • 可以把newtype定义的类型当作普通的类型使用，因为在编译期Nc值构造子是存在的
  • 但是有特例，比如模式匹配中
1
2
3
4
5
6
7
8
-- 对undefined进行求值会引发异常

-- 匹配时会对undefined进行求值，所以会产生异常
case undefined of Dc _ -> 1

-- 没异常，因为Nc实际是不存在的，'Nc x' will always have the same representation as 'x'
-- 因此等价于undefined匹配`_`，由于永远都会匹配成功，所以undefined不需要也不会被求值
case undefined of Nc _ -> 1

类型别名

  • 实际是基于原有的typeConstructor定义新的typeConstructor！但是并没有产生新的valueConstructor
1
2
-- <typeConstructor> 是引用的type/data中的定义
type <typeConstructor> <typeArg>* = <typeConstructor> <typeArg>*
1
2
3
4
5
6
7
8
9
type String = [Char]
type Entry k v = (k,v) -- (1,2) :: Entry Num Num
type EntryList k v = [Entry k v]
type EntryList k v = [(k,v)] -- [(1,2)] :: EntryList Num Num

-- 由于类型构造子的参数也可以部分指定，所以类似函数的point free style
type IntMap v = Map Int v
-- 可写成
type IntMap = Map Int
  • 使用别名能够增强函数类型的可读性
1
2
3
4
5
6
7
type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]

-- 判断指定的名字和号码是否在通讯录中
inPhoneBook :: Name -> PhoneNumber -> PhoneBook -> Bool
inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook

role

https://www.reddit.com/r/haskell/comments/3uvyed/acceptable_use_cases_of_coerce/

类型有三种role：

  • nominal. Nominal equality is type equality as we know it. GHC knows that Int is nominally equal to Int, but doesn’t know that Int is nominally equal to Char.

  • representational. Any two nominally equal types are also representationally equal, and in addition, a newtype is representationally equal to its underlying type. For example, GHC knows that Int is representationally equal to Int, and if you have newtype WrappedInt = WrapInt Int, then GHC knows that Int is representationally equal to WrappedInt.

  • phantom. Any two types are phantom equal.

指定类型的role：

1
type role <type> nominal

coerce :: Coercible a b => a -> b

GHC will infer that two types are Coercible if and only if they are representationally equal.

https://wiki.haskell.org/GHC/Coercible

Either 类型

  • 这个类型可以拥有两种不同类型，只能选择其中一个类型存一个值
1
data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show)
  • 用途之一就是，作为一个返回值。当代表成功时将结果存入Right，代表失败时将结果存入Left。这样对结果使用模式匹配就能知道调用是否成功，以及成功信息或者失败信息。

Maybe也可以表达失败（Nothing），但是没有失败信息

实例

定义一棵树

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

typeclass

类似于接口

  • 为类型（不只是kind为*的类型）归类一些共有的操作
  • 所有的typeclass都是一个类型构造子，但与一般的类型构造子不同，它最终构造的类型是Constraint而不是*。如class A a，A的kind是* -> Constraint
  • 使用:info <typeclass>或者:i <typeclass>查看typeclass信息
  • 可以查看该typeclass定义的函数和它的实例

定义typeclass

1
2
3
4
-- <constrains>引用自类型描述/类型注释

<typeVar> ::= [a-z].*
<typeclassDef> ::= class [<constrains> =>] <typeclass> <typeVar>+ where <defs>

  • <typeVar>代表的是此<typeclass>的一个instance（即某个typeConstructor，有参或无参），用于在需要这个类型时充当占位符

  • instance的kind是通过<typeclassDef>内部的<defs>中为c给予了几个参数来确定的（如x -> c a b -> y，那么c的kind是* -> * -> *，而x -> c a b -> c a则编译不通过）

  • <constrains>中对<typeVar>的constrain，表明了<typecalss>是另外某些typeclass的subclass，(<typeclass>的instance也必须是那些typeclass的instance，因此必须分别实现那些typeclass中的<defs>（存疑!）)

  • <defs>中可以声明函数类型，可以定义函数，还可以声明此typeclass的minimal complete definition（比如Num的{-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}，代表一个type至少得实现这些函数才能作为Num的实例）

为typeclass添加instance（instance都是type）

  • 一个type作为某个typeclass的一个instance代表，这个type（这个type未必是全调用的，例如当kind为* -> *时它的valueConstructor是一个函数）的valueConstructor能够参与这个typeclass声明的一些运算中
  • 当类型推导表示某个typeclass定义的某个运算使用到了这个类型的值，那么这个运算会使用这个instance中定义的运算的实现
  • 可以称作 <instance> 是一个 <typeclass>，就像Int是一个Num，(->) r是一个Functor
1
2
-- <type>是type/data中的，<typeclass>是typeclass中的，<constrains>引用自类型描述/类型注释
<instanceDef> ::= instance [<constrains> =>] <typeclass> <type> where <defs>
  • <defs>中的函数定义能替换typeclass的<defs>中相应的函数定义
  • 如果<defs>中使用到了某些typeclass的函数，<constrains>必须添加该typeclass的约束

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class (Eq a) => C a where
   add :: a -> a -> a

data I a = A a deriving(Show)

-- 基于上面的代码，使I a 是 C 的实例：

-- 由于Eq是C subclass，所以如果想要 I a 是C的实例，那么它也必须是Eq的实例
-- 由于用到了==判断a type的值是否相等，所以a必须是Eq的实例
instance (Eq a) => Eq (I a) where
    (A x) == (A y) = x == y

-- 由于我们上面的定义，只有a是Eq的实例时I a才会是Eq的实例，而又由于I a必须是Eq的实例，I a才能是C的实例，所以a必须是Eq的实例I a才能是C的实例。
必须A 才能 B
必须B 才能 C
所以：必须A 才能 C

-- 由于这里的I a必须同时都是Eq和C的实例，所以a必须是Eq的实例
为了B&&C 必须 A

-- 又由于用到了+对a type的值进行运算，所以a的必须是Num的instance
instance (Eq a, Num a) => C (I a) where
    (A x) `add` (A y) = A $ x + y
1
2
3
4
5
6
class C a where
   add :: a -> a -> a
data I a = A a deriving(Show)
-- 这里并不要求I a必须是Eq的实例，它可以单纯是C的实例但不是Eq的实例。
instance (Num a) => C (I a) where
    (A x) `add` (A y) = A $ x + y
1
2
3
4
5
6
7
8
9
data I a = I a deriving(Show)

instance (Num a) => Num (I a) where
    (I x) + (I y) = I $ x + y
    (I x) * (I y) = I $ x * y
    negate (I x) = I $ negate x
    abs (I x) = I $ abs x
    signum (I x) = I $ signum x
    fromInteger x = I $ fromInteger x

一些 typeclass

  • Enum：的实例：(), Bool, Char, Ordering, Int, Integer, Float 和 Double。每个值都有后继子 (successer) 和前置子 (predecesor)，分别可以通过 succ 函数和 pred 函数得到。
  • Bounded：成员都有一个上限和下限。如果Tuple中的项都属于 Bounded Typeclass，那么该 Tuple 也属于 Bounded。minBound 和 maxBound 函数，它们的类型都是 (Bounded a) => a
  • Num： 亲近Show 和 Eq，才可以加入 Num
  • Integral 同样是表示数字的 typeclass。Num 包含所有的数字：实数和整数。而 Integral 仅包含整数，其中的成员型别有 Int 和 Integer。
  • Floating实例：Float 和 Double。

Functor/Applicative/Monad 的实例

  • Maybe：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

instance Applicative Maybe where
    pure = Just

    Just f  <*> m       = fmap f m
    Nothing <*> _m      = Nothing

    liftA2 f (Just x) (Just y) = Just (f x y)
    liftA2 _ _ _ = Nothing

    Just _m1 *> m2      = m2
    Nothing  *> _m2     = Nothing

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (>>) = (*>)
  • (->) r：
1
2
3
4
5
6
7
8
9
10
instance Functor ((->) r) where
    fmap = (.)

instance Applicative ((->) r) where
    pure = const
    (<*>) f g x = f x (g x)
    liftA2 q f g x = q (f x) (g x)

instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r