FreeモナドでListを表現する

以下のtweetをそのままコンパイルしようとしたら、主にScalaの型推論の弱さのせいで全然コンパイル通らなかったので、とりあえずコンパイル通るようにしたものを貼っておくだけ。

type List[A]=Free[({type f[x]=Option[(x,x)]})#f,A];def nil=Suspend(None);def cons[A](head:A,tail:List[A])=Suspend(Some(Return(head)->tail))

2013-11-23 12:54:36 via web

そもそも、これでListを表現できているのか、個人的に理解できてないので、(あとで気が向いたら、Listに関する関数を付け足したりして)色々やってみるつもり。

import scalaz._, Free._

object FreeMonadList {

  type PairOpt[α] = Option[(α, α)]

  type List[A] = Free[PairOpt, A]

  implicit val pairOptFunctor: Functor[PairOpt] =
    new Functor[PairOpt]{
      def map[A, B](fa: PairOpt[A])(f: A => B) = fa match{
        case Some((_1, _2)) => Some((f(_1), f(_2)))
        case None => None
      }
    }

  def nil[A]: List[A] = Suspend[PairOpt, A](None)

  def cons[A](head: A, tail: List[A]): List[A] =
    Suspend[PairOpt, A](Option(Return[PairOpt, A](head) -> tail))
}

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.1.0-M3"

scalaVersion := "2.10.3"

追記:
最近のScalazでは上記コード動かなくなってたので、修正版 https://gist.github.com/xuwei-k/31c2317a5b9035932399