上一次的从Functor开始,然后到Applicative,最后到sequenceA的实现。

Kinds and some type-foo

之前的内容只关注构建自己的Types以及Typeclasses但是并没有特别讨论kinds以及types

Types可以看做values上带着的小标签,我们通过这个标签来获取一些诸如判断如何操作使用的信息。而Types本身也有这样的标签叫做Kinds

ghci里面使用:k命令可以可以查看typekind。在scala console里,也可以同样查看类型。

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
scala> :k Int
scala.Int's kind is A
scala> :k -v Int
scala.Int's kind is A
*
This is a proper type.
scala> :k -v Option
scala.Option's kind is F[+A]
* -(+)-> *
This is a type constructor: a 1st-order-kinded type.
scala> :k -v Either
scala.util.Either's kind is F[+A1,+A2]
* -(+)-> * -(+)-> *
This is a type constructor: a 1st-order-kinded type.
scala> :k -v Equal
scalaz.Equal's kind is F[A]
* -> *
This is a type constructor: a 1st-order-kinded type.
scala> :k -v Functor
scalaz.Functor's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

从最上面开始,Int以及其他具体类型,都用*表示,在scala里面采用A来表示,first-order value,像(_: Int) + 3这种函数,或者如OptionEither这种type constructor,我们使用诸如*->*或者*->*->*。值得注意的是,Option[Int]就是*,而Option才是*->*。用scala的类型变量声明就是F[+A]F[+A1,+A2]

higher-order value(f: Int => Int, list: List[Int]) => list map {f}这种高阶函数,是一种接受其他type constructortype constructor。类型如(* -> *) -> *,或者可以写成X[F[A]]

scalaz 7.1中,Equal以及其他一些的类型的kindF[A],而Functor以及其他从它派生而来的类型的kindX[F[A]]。Scala倾向于交叉着使用type classtype constructor,一些术语显得有些混乱。比如,List本身符合Functor的性质,而事实上Functor[List]可以从List派生出来,所以我们说List is a functor

In FP, “is a” means “a instance can be derived from.” @jimduey # CPL14 It’s a provable relationship, not reliant on LSP.

由于List的kindF[+A],所以很容易意识到F对应于Functor。此外,Functor作为typeclass的定义需要在F[A]外面再包一层,就变成了X[F[A]]。scala本身可以把类型当做变量来使用比如

1
2
3
trait Test {
type F[_]
}

一般来说,在你直接使用那些诸如的操作的时候不用关心这些细节,但是当你想要通过类型的伴生对象进行一些操作的时候,就需要注意了。比如

1
2
3
4
5
6
7
8
9
10
11
// 通过注入调用
List(1,2,3,4).shows
// 通过伴生对象调用
Show[List[Int]].show(List(1,2,3,4))
// 应该是 Functor[List]即X[F[_]]
Functor[List].lift((_: Int) + 2)
// error: List[Int] takes no type parameters, expected: one
Functor[List[Int]].lift((_: Int) + 2)

Tagged type

在《Learn You a Haskell for Great Good》中有提到

The newtype keyword in Haskell is made exactly for these case when we want to just take one type and wrap it in something to present it as another type

这在Haskell中是个语言级的特性,我们可以试一试在scala中实现对应的东西。

考虑一个应用场景,我们想要表示物体的重量,使用kg作为标准单位。一般来说,我们希望传入一个Double,然后使用它。一般来说我们可以

1
case class KiloGram(value: Double)

但是这样虽然可以保证类型安全,但是每次使用的时候都要使用x.value的形式。scalaz里面提供了@@

1
2
3
4
5
6
7
8
9
sealed trait KiloGram
def KiloGram[A](a: A): A @@ KiloGram = Tag[A, KiloGram](a)
val mass = KiloGram(20.0)
30 * Tag.unwrap(mass)
2 * scalaz.Tag.unsubst[Double, Id, KiloGram](mass)

@@的实现大致如

1
2
private[scalaz] type Tagged[A, T] = {type Tag = T; type Self = A}
type @@[T, Tag] = Tagged[T, Tag]

它构件了一个新的类型,其中Tag用来标注我们给的带有含义的类型比如KiloGram,然后T用来代表具体的类型比如这里的Double。通过A @@ KiloGram来构件新的类型。

现在,我们可以定义根据\(E=mc^2\)求能量的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sealed trait KiloGram
def KiloGram[A](a: A): A @@ KiloGram = Tag[A, KiloGram](a)
val mass = KiloGram(20.0)
sealed trait JoulePerKiloGram
def JoulePerKiloGram[A](a: A): A @@ JoulePerKiloGram = Tag[A, JoulePerKiloGram](a)
def energyR(m: Double @@ KiloGram): Double @@ JoulePerKiloGram =
JoulePerKiloGram(299792458.0 * 299792458.0 * Tag.unwrap(m))
energyR(mass)
// res: scalaz.@@[Double,JoulePerKiloGram] = 1.79751035747363533E18
energyR(20) // error type mismatch

正如上面代码展示的,我们直接传递Double的时候会在编译期就触发错误。

About those Monoids

显然*和1与++Nil有很多相似的性质,比如

1
2
3
4
5
4*1 == 1*4
Nil ++ List(1,2,3) == List(1,2,3) ++ Nil
(3 * 2) * 4 == 3 * (2 * 4)
(List("la") ++ List("di")) ++ List("da") == List("la") ++ (List("di") ++ List("da"))

满足幺元的性质,满足结合律。

monoid

A monoid is when you have an associative binary function and a value which acts as an identity with respect to that function.

我们来看看scalazMonoid的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
trait Monoid[F] extends Semigroup[F] { self =>
////
/** The identity element for `append`. */
def zero: F
// derived functions
/**
* For `n = 0`, `zero`
* For `n = 1`, `append(zero, value)`
* For `n = 2`, `append(append(zero, value), value)`
*/
def multiply(value: F, n: Int): F =
if (n <= 0) zero else multiply1(value, n - 1)
Semigroup

monoid继承自semigroup

1
2
3
4
5
6
7
8
9
10
trait Semigroup[F] { self =>
def append(f1: F, f2: => F): F
...
}
final class SemigroupOps[F] private[syntax](val self: F)
(implicit val F: Semigroup[F]) extends Ops[F] {
final def |+|(other: => F): F = F.append(self, other)
final def mappend(other: => F): F = F.append(self, other)
final def (other: => F): F = F.append(self, other)
}

先看看mappend函数。

We have mappend, which, as you’ve probably guessed, is the binary function. It takes two values of the same type and return a value of that type as well.

不过虽然他的名字叫mappend,也不意味着一定是把什么东西连起来,只是集合上的乘法运算而已。

1
2
List(1,2,3) mappend List(4,5,6)
"one" |+| "two"

Back to Monoid

重新看一下Monoid

1
2
3
4
trait Monoid[F] extends Semigroup[F] { self =>
////
/** The identity element for `append`. */
def zero: F

mempty represents the identity value for a particular monoid.

这里的memptyscalaz里面就叫zero,我们可以看看这些zero都是什么。

1
2
Monoid[List[Int]].zero // res: List[Int]=List()
Monoid[String].zero // res: String=""

Tags.Multiplication

So now that there are two equally valid ways for numbers (addition and multiplication) to be monoids, which way do choose? Well, we don’t have to.

所以在scalaz 7.1中,存在tagged type。其中有8个针对Monoids的tag,以及1个叫做Zip的为Applicative的tag。

比如

1
2
3
4
5
6
7
8
Tags.Multiplication(10) |+| Monoid[Int @@ Tags.Multiplication].zero
// res0: scalaz.@@[Int,scalaz.Tags.Multiplication] = 10
Tags.Multiplication(10) |+| Tags.Multiplication(3)
// res1: scalaz.@@[Int,scalaz.Tags.Multiplication] = 30
10 |+| Monoid[Int].zero
// res2: 10
10 |+| 3
// res3: 13

Tags.Disjunction and Tags.Conjunction

另外一种可以采用两种不同的方式满足Monoid的类型是Bool。第一种方法是用or当做运算,用False当做identity value,另一种是用and当做运算,用True当做identity value

scalaz 7里面,使用DisjunctionConjunction两种方式来区别。

1
2
3
4
5
6
7
8
9
10
11
Tags.Disjunction(true) |+| Tags.Disjunction(false)
// res0: scalaz.@@[Boolean,scalaz.Tags.Disjunction] = true
Monoid[Boolean @@ Tags.Disjunction].zero |+| Tags.Disjunction(true)
// res1: scalaz.@@[Boolean,scalaz.Tags.Disjunction] = true
Tags.Conjunction(true) |+| Tags.Conjunction(false)
// res2: scalaz.@@[Boolean,scalaz.Tags.Conjunction] = false
Monoid[Boolean @@ Tags.Conjunction].zero |+| Tags.Conjunction(false)
// res3: scalaz.@@[Boolean,scalaz.Tags.Conjunction] = false

Ordering as Monoid

Ordering同样也是Monoid

1
2
3
4
5
6
7
8
9
10
(Ordering.LT: Ordering) |+| (Ordering.GT : Ordering)
// res0: scalaz.Ordering = LT
(Ordering.GT: Ordering) |+| (Ordering.LT : Ordering)
// res1: scalaz.Ordering = GT
Monoid[Ordering].zero |+| (Ordering.LT : Ordering)
// res2: scalaz.Ordering = LT
Monoid[Ordering].zero |+| (Ordering.GT: Ordering)
// res3: scalaz.Ordering = GT
(Ordering.EQ : Ordering) == Monoid[Ordering].zer
// res4: Boolean: true

这里EQ是幺元,而操作是当第一个为EQ时,返回第二个结果,否则返回第一个结果。

Monoid到底有什么用呢?比如我们想要比较两个字符串的长度,但是当他们长度相等的时候,就比较字母顺序。就可以这么实现。

1
2
3
4
5
6
7
8
9
def lengthCompare(lhs: String, rhs: String): Ordering =
(lhs.length ?|? rhs.length) |+| (lhs ?|? rhs)
lengthCompare("zen", "ants")
// res0: scalaz.Ordering = LT
lengthCompare("ans", "ans")
// res1: scalaz.Ordering = EQ
lengthCompare("zen", "ant")
// res2: res2: scalaz.Ordering = GT



X