Shapelessの紹介

class: center, middle

# Shapelessの紹介

2014年10月25日
[函数型なんたらの集い 2014](https://connpass.com/event/8634/)

---
class: middle

- twitter [@xuwei_k](https://twitter.com/xuwei_k)
- github [@xuwei-k](https://github.com/xuwei-k)
- blog <https://xuwei-k.hatenablog.com/>

---
class: middle

<https://github.com/scalaz/scalaz/graphs/contributors?from=2013-01-01&to=2013-12-31&type=c>

![2013](./scalaz2013.png)

---
class: middle

<https://github.com/scalaz/scalaz/graphs/contributors?from=2014-01-01&to=2014-10-25&type=c>

![2014](./scalaz2014.png)

---
class: middle

## オープンソース活動

- (2014-10-25日現在)2年連続Scalazのコミット数1位

---
class: middle

## 現実(仕事)

<blockquote class="twitter-tweet" lang="en">毎日テストに Thread.sleep 書いてる気がする・・・— Kenji Yoshida <a href="https://twitter.com/xuwei_k/status/499418167697866754">August 13, 2014</a></blockquote>

---
class: middle

## 現実(仕事)

<blockquote class="twitter-tweet" lang="en">Scala祭明けの、最初の仕事のコミットです

git commit -a -m "テストがJenkins上だと稀に失敗するので、Thread.sleepを追加"— Kenji Yoshida <a href="https://twitter.com/xuwei_k/status/509182633587130368">September 9, 2014</a></blockquote>

---
class: middle

- ニコニコの色んなサービスの裏側をScalaやAkkaで作ってます
- 今のところ [Scalacheck(QuickcheckのScala版)](https://github.com/rickynils/scalacheck) と、それに伴いScalazを少しテストコードに混ぜ込むくらいしかやってない

---
class: middle

- Scalaにおける函数型プログラミングといえば、Scalazがあまりにも有名
- [勉強会もやりました](https://connpass.com/event/7261/)
- しかし今日は、Scalazの話も少しするけど、主にそれ以外の話をします

---
class: middle, center

<pre style="font-size: 350%;">
＿人人人人人人＿
＞　shapeless　＜
￣Y^Y^Y^Y^Y￣
</pre>

---
class: middle, center

<https://github.com/milessabin/shapeless>

---
class: middle, center

Scalazが扱わない函数型な領域を扱う Scalaにおけるラスボス的な何か(勝手なイメージ)

---
class: middle

- ただし一部Scalazと重複してるものもある
- 重複していたけど、shapelessのほうが優れているものは、Scalazから消された

---
class: middle

## 個人的に

- shapeless本体には、今のところ1コミットもしたことない
- Scalazコミッターの自分ですら、かなり難しいと感じる

---
class: middle

## なぜScalazに慣れていても難しいと感じるのか考えてみた

---
class: middle

## 難しさ？の原因

- dependent method type(とimplicitの組み合わせ)
- macro

---
class: middle

<https://github.com/milessabin/shapeless/blob/b34d0f/core/src/main/scala/shapeless/alacarte.scala#L162-L172>

![implicit8](./implicit8.png)

---
class: middle

- Scalazは現時点(7.1.0)ではmacro全く使ってない
- dependent method typeもあまり使ってない?
    - Scalazで使ってる例 [Unapply](http://eed3si9n.com/learning-scalaz/ja/Unapply.html)

---
class: middle, center

## READMEの記述

implementing
scrap your boilerplate and
higher rank polymorphism in Scala

---
class: middle

## [scrap your boilerplate](https://research.microsoft.com/en-us/um/people/simonpj/papers/hmap/)
 - Haskellの有名なアレ
 - 一部移植した例 <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/examples/src/main/scala/shapeless/examples/sybclass.scala>

---
class: middle

## higher rank polymorphism

- 論文のリンクっぽいけどリンク切れ・・・
- RankNとかそういうの？

---
class: middle, center

代表的な機能一覧はwikiにまとまってる

<https://github.com/milessabin/shapeless/wiki/Feature-overview:-shapeless-2.0.0>

---
class: middle, center

もしくはサンプルコードがある程度豊富

<https://github.com/milessabin/shapeless/tree/shapeless-2.0.0/examples/src/main/scala/shapeless/examples>

---
class: middle

- コレ書いてる現在の最新安定版 2.0.0
- 2.0.0がでてから結構経過していて、masterとはわりと異なるので注意

---
class: middle, center

ここから、大雑把にwikiに載っていた ものを中心に解説

---
class: middle, center

## Polymorphic function values

---
class: middle, center

---
class: middle

- Scalazやsbtにもある(記号もみんな同じ)
- Scalazのものより、この函数を使えるものが豊富だったりするかも
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/poly.scala#L142>

---
class: middle

例えば `List[A]` (任意のA) から `Option[A]` への函数

```scala
val headOption: List ~> Option =
  new (List ~> Option){
    def apply[A](a: List[A]) =
      a.headOption
  }
```

---
class: middle

## Heterogenous lists

- みんな大好き?HList
- Scala界隈では、Tuple22制限などの影響で、いくつかのライブラリでHListの再発明が
- 色んなメソッドがあったり機能豊富という意味では一番優れてる(と思う)

---
class: middle

## Heterogenous lists

- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/hlists.scala>
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/ops/hlists.scala>

---
class: middle

## HListの機能の豊富さ

- HListに型レベル自然数を渡すことにより、型安全にN番目の要素が取れるとか当たり前

---
class: middle

## その他HListの メソッド達(一部)

head, tail, cons, ++, reverse, last, init, filter, replace, updateWith, take, drop, split, reverse, map, flatMap, foldMap, foldLeft, foldMap, zip
    
---
class: middle

- これらのメソッドが全部 dependent method type と implicit で作られているので、型シグネチャがやばい
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/syntax/hlists.scala>

---
class: middle

## HList-style operations on standard Scala tuples

- Tupleを自動でHListっぽく扱える機能

---
class: middle

- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/syntax/std/tuples.scala>
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/ops/tuples.scala>
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/test/scala/shapeless/tuples.scala>

---
class: middle

## Heterogenous maps

---
class: middle, center

---
class: middle

- KeyとValueの型の組み合わせ規則を定義すると、どんな型のKeyとValueも型安全に詰め込めるMap
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/hmap.scala>
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/test/scala/shapeless/hmap.scala>

---
class: middle

### Singleton-typed literals, Singleton-typed Symbols, Extensible records

- Scalaの謎仕様を最大限悪用(?)したヤバイやつ
- 一言で言うと、無名case classが簡単に作れる
- <https://xuwei-k.hatenablog.com/entry/20140718/1405581087>

---
class: middle

```scala
$ scala
Welcome to Scala version 2.11.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_11).
Type in expressions to have them evaluated.
Type :help for more information.
 
scala> val a = "a"
a: String = a
 
scala> final val b = "b"
b: String("b") = b
 
scala> def foo(c: b.type) = c
foo: (c: String("b"))String
 
scala> foo("bar")
<console>:10: error: type mismatch;
 found : String("bar")
 required: String("b")
 foo("bar")
 ^
 
scala> foo("b")
res1: java.lang.String = b
```

---
class: middle

関連して、将来的に

と書けるようになるかもしれないという話がある

[SIP-23 - Literal-based singleton types](https://docs.scala-lang.org/sips/pending/42.type.html)

---
class: middle

## Extensible records

- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/records.scala>
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/syntax/records.scala> 
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/examples/src/main/scala/shapeless/examples/records.scala>

---
class: middle

## Coproducts and discriminated unions

- Union型と言えばいいのだろうか・・・
- 任意の数の型の組み合わせを自分で定義して、それを一つの型として扱える
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/coproduct.scala>

---
class: middle
## Coproducts and discriminated unions

- 例えば「`Int`か`String`か`Boolean`のどれか」という感じ
- これ単体でも使えるが、shapeless内の他のclassと密接に関連している

---
class: middle

- [CoproductとInjectを使ったFree Monadの合成とExtensible Effects](https://xuwei-k.hatenablog.com/entry/20140618/1403054751)
- [ScalazのCoproductの代わりに、shapelessのものを使うと便利かも？](https://github.com/mandubian/injective/blob/bc57d09d/src/test/scala/InjectiveSpec.scala#L63)

---
class: middle

## Generic representation of (sealed families of) case classes

- GHC7.2以降に入っている Generics と似てる、と書いてある
- <https://www.haskell.org/haskellwiki/GHC.Generics>

---
class: middle

- 自動で、case classとHListの相互変換のためのオブジェクトが手に入る
- 実装はマクロ
- sealed classやtraitなら?その子供のclassも含めて考慮

---
class: middle

- LabelledGeneric という、case classのフィード名もマクロで取得してきて汎用的に利用できる機能とか
- 後で話すが、型クラスのインスタンスの自動生成に利用

---
class: middle

## Boilerplate-free lenses for arbitrary case classes

- ScalaにはLensのライブラリいっぱい・・・
- shapelessのものは、マクロ使っていて、定義が短く書けて便利

---
class: middle

## First class lazy values tie implicit recursive knots

- 自己のインスタンス定義に、自分のインスタンスが必要という再帰的構造の場合に、Scalaではうまくいかない
- 例えば、FreeやCofreeのEqの定義

---
class: middle

- そういった問題を解決
- マクロで実装されてる
- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/lazy.scala>

---
class: middle

- <https://xuwei-k.hatenablog.com/entry/20131223/1387798959> 問題点を別の方法で解決を試みた
- <https://github.com/xuwei-k/scalaz/commit/8f4a0fb7ee44732c> Scalazに直接入れてみた例
- <https://github.com/typelevel/shapeless-contrib/pull/9/files> shapeless-contribというのに入れた

---
class: middle

## Collections with statically known sizes

- サイズが型レベルで決まっているList
- HListとは違い、要素の型は全部同じ

---
class: middle

## Type safe cast

- HaskellにおけるTypeableっぽいことがある程度可能らしい？

---
class: middle

## Testing for non-compilation

- マクロによって「コンパイルが通らない」ことがテストできる
- 最近はScalatestとかにもある

---
class: middle, center

## Zipper

普通のZipperではなく、HListに関連するもの

---
class: middle, center

その他にもまだ紹介できてない機能あるかも

---
class: middle

## 型クラスのインスタンスの 自動生成の話

---
class: middle, center

これ読めばよい

<https://typelevel.org/blog/2013/06/24/deriving-instances-1.html>

---
class: middle

## 自動生成できる型クラスの種類

- Scalazだと例えば以下のようなやつ
    - `Semigroup`
    - `Monoid`
    - `Equal`
    - `Order`
    - `Show`

---
class: middle

- つまり、Haskellの標準の範囲と同じ?で、Kindが`Eq`と同じやつ
- `Functor` とかはできない
- あれどういうアルゴリズムでやってるんですか、教えてください・・・ 
    
---
class: middle

ちなみに、newtypeの場合は(ある程度Haskellより面倒だが) `deriving Functor` 相当の仕組みはScalaz自体に存在する

---
class: middle

- 実際のライブラリはこちら
- <https://github.com/typelevel/shapeless-contrib/tree/v0.3/scalaz/main/scala>
- Scalaz以外にも対応可能
 - spire
 - scalacheck
 - その他自分で定義すれば(kindが`Eq`と同じならば)

---
class: middle

## 内部の構造とか作り方の説明

- <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/typeclass.scala>
- `なんとかTypeClass` という、型クラスをderivingするための型クラス、というメタ的な何か

---
class: middle

- 例えば
    - `TypeClass[Equal]`
    - `ProductTypeClass[Monoid]`
- Haskellではコンパイラ(GHC)が勝手にやってくれるので、対応する型クラスは存在しない

---
class: middle

- 4種類
    - ProductTypeClass
    - TypeClass
    - LabelledProductTypeClass
    - LabelledTypeClass

---
class: middle

---
class: middle

- Labelledとは、case classのfield名を使うか否か
- 例えば、case classに対して、JsonのEncode、Decodeのための型クラスのインスタンスを自動生成したい

---
class: middle

- その場合に、field名をそのままJsonのKeyにしたい
- <https://github.com/argonaut-io/argonaut/pull/128/files>

---
class: middle

## Productが付いているか いないかの違い

- 継承関係から分かるように、Productがついていないほうが強い(できることが多い)

---
class: middle, center

ProductTypeClassのみでEqualの インスタンスの自動生成が可能

```scala
final case class Person(id: Int, name: String)
```

---
class: middle

- `ProductTypeClass` のみでderiving不可能
- `TypeClass[Equal]` が必要

```scala
sealed trait Tree[T]
case class Leaf[T](t: T) extends Tree[T]
case class Node[T](l: Tree[T], r: Tree[T]) extends Tree[T]
```

(もちろん、型パラメータの <code>T</code> の <code>Equal</code> のインスタンスが存在する場合)

---
class: middle

## その他便利な応用例

---
class: middle, center

<code>F[_]</code> が `Applicative`

なら

を

に変換可能(逆も可能)

---
class: middle

例1

```scala
Option[Int] :: Option[String] :: HNil

Option[Int :: String :: HNil]
```

---
class: middle

例2

```scala
Either[Int, String] :: Either[Boolean, String] :: HNil

Either[Int :: Boolean :: HNil, String]
```

---
class: middle

つまり、Haskellにおける`Traversable`の`sequenceA`などが`HList`に対して可能

<https://hackage.haskell.org/package/base-4.7.0.1/docs/Data-Traversable.html#v:sequenceA>

---
class: middle

[252要素のcase classまでのplayframeworkのJsonのReadsやWritesやFormatを生成できるライブラリ作った](https://xuwei-k.hatenablog.com/entry/20140727/1406445058)

---
class: middle

<blockquote class="twitter-tweet" data-lang="en">こういう感じのコード生成してコンパイル始めたら、Scalaコンパイラさんが数十分ずっとコンパイルしてて終わらない・・・ <a href="https://t.co/TNp92zYvO5">pic.twitter.com/TNp92zYvO5</a>— Kenji Yoshida (@xuwei_k) <a href="https://twitter.com/xuwei_k/status/492998634011521024">July 26, 2014</a></blockquote>

---
class: middle

<blockquote class="twitter-tweet" lang="en"><a href="https://twitter.com/xuwei_k">@xuwei_k</a> 結果、1時間くらいコンパイル時間がかかるようになってしまって全く実用的ではないので、(どうせimplicitの探索が遅いのだろうから)implicitをすべて明示的に呼び出してコンパイル時間の短縮を試みるというScalaコンパイラへの思いやりあふれる作業している— Kenji Yoshida (@xuwei_k) <a href="https://twitter.com/xuwei_k/status/493045911627390976">July 26, 2014</a></blockquote>

---
class: middle

<blockquote class="twitter-tweet" lang="en"><a href="https://twitter.com/xuwei_k">@xuwei_k</a> what are you doing!?!— Miles Sabin (@milessabin) <a href="https://twitter.com/milessabin/status/493094054696341504">July 26, 2014</a></blockquote>

---
class: middle

- なにも考えないで実装すると、1時間経ってもコンパイル終わらないコードが出来上がる
- 頑張っても10分以上かかる
- ソースコードが13MB, バイナリ11MB

---
class: middle

- shapeless作者から "what are you doing!?!" というmentionくる 
- C++メタプログラミングのように、コンパイル時のアルゴリズムのオーダーとか考える必要

---
class: middle

## その他雑多な話 exampleの紹介など

---
class: middle

## typelevel fibonacci

<https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/examples/src/main/scala/shapeless/examples/fibonacci.scala>

---
class: middle

## typelevel FizzBuzz

<https://gist.github.com/travisbrown/4108026>

---
class: middle, center

[Boxy Types: Inference for Higher-Rank Types and Impredicativity](https://research.microsoft.com/en-us/um/people/simonpj/papers/boxy/boxy-icfp.pdf)
という Simon Peyton Jonesセンセの論文

の一部をshapelessでやってみたもの?

<https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/examples/src/main/scala/shapeless/examples/impredicative.scala>

---
class: middle

## shepelessを使ってる ライブラリ

---
class: middle

## scodec

- <https://github.com/scodec/scodec>
- バイナリデータなどをEncode, Decodeするライブラリ
- shapeless結構使ってる

---
class: middle

## scodec

![scodec](./scodec.png)

---
class: middle

## spray

- routingまわりで使われているらしい
- <https://github.com/spray/spray/blob/v1.3.2/spray-routing/src/main/scala/spray/routing/HListDeserializer.scala>

---
class: middle

## akka-http

- よってsprayから移植されたakka-httpにもある
- <https://github.com/akka/akka/tree/akka-stream-and-http-experimental-0.9/akka-parsing/src/main/scala/akka/shapeless>

---
class: middle

## parboiled2

- マクロを大量に使ってる、PEG Parser
- <https://github.com/sirthias/parboiled2>
- 個人的にあまり詳しくないのでわからない・・・(´･_･`)

---
class: middle

## http4s

- Scalatraの人達が、次期Scalatraの内部で使うために、色々とかなり低レベルなところからscalaz-stream使い作成中のなにか
- parboiled2経由で少し使ってる？
- <https://github.com/http4s/http4s>
- もみあげさん [@pocketberserker](https://twitter.com/pocketberserker) が、少し詳しい？

---
class: middle

## まとめ?

- ただでさえ遅いコンパイル時間が更に長く！
- 型がとにかくヤバイ、けどその分とにかくスゴイ
- ソース読むとマクロ関連のバグのURLいくつかあったりして怖い
 - <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/generic.scala#L219>
 - <https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/syntax/records.scala#L40>