Heterogeneous List简单来说就是即能像tuple一样包含不同类型的元素,又能像List一样提供append等操作。

HList是个很有用的数据结构,尤其是它上面定义了mapfoldr这种函数,通过natural transformation可以进行更多的操作。诸如知乎上这个问题。在那些本来是使用tuple,但是由于scheme不固定,如果想要适配多种情况,不然运行时反射类型,不然就得写很多样板代码。

Basic

对比HListList,其实区别在于List每次加入新的node并不改变类型,而HList需要更改自己的类型,从而保证类型约束。

1
2
3
4
5
sealed abstract class HList
final case class HCons[H, T <: HList](head: H, tail: T) extend HList
object HNil extends HList

基础的结构就是这样了。其实这样一看无非就是每次都把新的类型利用HList这个容器加进去。

比如一个1::1.2::"hello":HNil的类型就变成了HCons[Int, HCons[Double, HCons[String, HNil.type]]]

既然这样,就可以容易的得到添加操作。这里定义成:+:

1
def :+:[A](v: A): HCons = HCons(v, this)

可以试一下

1
2
3
1 :+: 1.2 :+: "hello" :+: HNil
// res0: HCons[Int, HCons[Double, HCons[String, HNil.type]]] =
// HCons(1,HCons(1.2,HCons(hello,hlist.HNil$@5a996f9e)))

fold

定义了新的类型,就需要类型上的操作,要实现各种操作,不是实现fold就是需要flapMap,这里就先实现foldr

先尝试把类型签名写出来,对比一下普通的foldr

1
def foldr[A, B](a: List[A])(z: B)(f: (A, B) => B): B

我们的foldr也应该是这样

1
def foldr[Value, T <: Value](f: ???, i: T): ??? = f(head, tail.foldr(f, i))

现在问题来了,这个里面的???类型怎么写?由于每个节点的类型都不一样,所以f的类型,以及最后返回的类型,都应该是不一样的。

类型的函数

type-level当然就要对类型的操作也抽象一个函数出来了,我们定义操作f的类型为Fold,他应该接受一个当前节点,返回一个foldr之后的类型。

1
2
3
4
trait Fold[-Elem, Value] {
type Apply[N <: Elem, Acc <: Value] <: Value
def apply[N <: Elem, Acc <: Value](n: N, acc: Acc): Apply[N, Acc]
}

其中Apply作为type-level的函数,接受两个类型,返回实际应用函数apply的返回类型,这样我们在实现自己的函数的时候,就可以同时提供一个type-level的函数,同时提供一个普通的函数了。

最后,就是

1
2
3
4
5
6
7
8
9
10
11
12
13
trait Fold[-Elem, Value] {
type Apply[N <: Elem, Acc <: Value] <: Value
def apply[N <: Elem, Acc <: Value](n: N, acc: Acc): Apply[N, Acc]
}
final case class HCons[H, T <: HList](head : H, tail : T) extends HList {
def :+:[A](v: A): HCons[A, HCons[H, T]] = HCons(v, this)
type Foldr[Value, F <: Fold[Any, Value], I <: Value] = F# Apply[H, tail.Foldr[Value, F, I]]
def foldr[Value, F <: Fold[Any, Value], I <: Value](f: F, i: I): Foldr[Value, F, I] =
f(head, tail.foldr[Value, F, I](f, i))
}

用foldr实现append

接下来就用foldr实现一个append函数,append的操作零是连接的HList,返回值也是一个HList,接下来就是实现一个连接的Fold

1
2
3
4
5
6
type :+:[H, T <: HList] = HCons[H, T]
object AppHCons extends Fold[Any, HList] {
type Apply[N <: Any, H <: HList] = N :+: H
def apply[A,B <: HList](a: A, b: B) = HCons(a, b)
}

其中type-levelApply,就直接把新类型连接到HList之上就行.

Map

这里实现有点勉强,这些坑也懒得大改了。

有了foldr,就可以实现map了。对比一下一般的实现。

1
2
def map[A, B](l :List[A])(f: A => B): List[B] =
l.foldRight(List[B]())((x, y) => f(x) :: y)

其实这里有个问题,就是由于每个元素的类型不同,所以map的函数本身肯定是带有泛型参数的。

所以类型应该是T -> F[_]这种样子的。

我们先一步一步的来,首先构造一个F[]->G[],(在这里我们可以不从这开始,不过这个也是有意义的)

1
2
3
4
trait ~>[F[_], G[_]] {
type Apply1[X] = G[X]
def apply1[T](f: F[T]): G[T]
}

然后由于我们要映射的其实是实际的类型所以我们使用

1
type Id[T] = T

然后就可以构造一个

1
type ~>>[G[_]] extends ~>[Id, G]

这就是我们要的map的参数类型了。但是我们是要通过foldr实现map的,所以,显然要实现一个Fold。他同时也应该是~>>

1
2
3
4
5
6
7
8
9
10
type HMap[A <: HList, G[_]] =
A# Foldr[HList, MapHCons[G] , HNil.type]
abstract class MapHCons[G[_]] extends Fold[Any, HList] with ~>>[G]{
type Apply[N <: Any, H <: HList] = (Apply1[N] :+: H)
def apply[A, B <: HList](a: A, b: B) = {
HCons(apply1(a), b)
}
}

这样,每次需要Map的时候,是要继承MapHCons,然后实现其中apply1函数,就可以使用了。

一个栗子

假如我们需要这么一个奇怪的函数,对于数字,我们想要知道他整数部分的长度,对于string或者List就直接关心他们的长度。

所以这个函数的map应该是A => Int,但是不太对啊,我们不是使用的是G[_],对于具体类型还能通过Id来转换,但是对于一个常量类型改怎么办呢?

1
2
3
type Const[C] = {
type lambda[T] = C
}

这样一个Int的常量就可以写成Const[Int]# lambda了,

进一步

1
2
3
4
5
6
7
8
object ToInt extends MapHCons[Const[Int]# lambda] {
override def apply1[T](f: T): Const[Int]# lambda[T] = f match {
case f: Int => f.toString.length
case s: String => s.length
case l: List[_] => l.length
case d: Double => d.toInt.toString.length
}
}

这样就可以实现

1
2
3
val a = 1 :+: 3.0 :+: "aiiiii" :+: List('r','H') :+: HNil
val f = a.map[Const[Int]# lambda, ToInt.type ](ToInt)
println(f.tail.head) // 6

这样就可以用了。

(不过,这里用了Any,其实还是在某种程度上忽略了类型信息。反正我实现一些参数的时候很麻烦。还是去看看shapeless靠谱。全部的代码可以看这里




X