Scalaz ListW

少し間が空いてしまいましたが、今度はScalazのListWです。数も多いので、けっこう大変でした。
あと、モナドを使用するAPIは理解できていません。

では、アルファベット順に。

<^>

元のListがNilでなければ、NonEmptyListが渡ってくるので、それに対して演算した結果が戻り値になります。

NonEmptyListは、必ず要素がある（＝Nilでない）Listです。

とりあえず、foldLeftしてみました。

  println("List(1, 2, 3) <^> foldLeft(0)(_ + _) => " + {
    List(1, 2, 3) <^> { nonEmptyList => nonEmptyList.list.foldLeft(0)(_ + _) }
  })
  println("Nil[Int] <^> foldLeft(0)(_ + _) => " + {
    nil[Int] <^> { nonEmptyList => nonEmptyList.list.foldLeft(0)(_ + _) }
  })

実行結果。

List(1, 2, 3) <^> foldLeft(0)(_ + _) => 6
Nil[Int] <^> foldLeft(0)(_ + _) => 0

breakM

M[Boolean]でListを分割します。Mって？モナド（Monad）のことっぽいのですが、これとAPIの噛み方がイマイチ分かっていません。

とりあえず、Option（Maybeモナドってこと？）で割れます。

  println("List(1, 2, 3, 2, 1) breakM some(_ > 2) => " + {
    List(1, 2, 3, 2, 1) breakM { elm => some(elm > 2) }
  })
  println("List(1, 2, 3, 2, 1) breakM none => " + {
    List(1, 2, 3, 2, 1) breakM { elm => none[Boolean] }
  })
  println("Nil[Int] breakM some(elm > 2) => " + {
    nil[Int] breakM { elm => some(elm > 2) }
  })
  println("Nil[Int] breakM none => " + {
    nil[Int] breakM { elm => none[Boolean] }
  })

なお、some、noneはそれぞれSome、Noneを生成する関数です。noneは、型パラメータを指定できるところがポイントですね。

実行結果。

List(1, 2, 3, 2, 1) breakM some(_ > 2) => Some((List(1, 2),List(3, 2, 1)))
List(1, 2, 3, 2, 1) breakM none => None
Nil[Int] breakM some(elm > 2) => Some((List(),List()))
Nil[Int] breakM none => Some((List(),List()))

Some[Boolean]がSome(true)となるもの、Some(false)となるものでListが分割され、さらにSomeでくるんで返されます。falseを返していた時の要素が、最初のListに入ります。
Noneとすると、戻り値もNoneになります。
Nilに対して適用すると、Someに包まれた2つのNilが返ります。

filterM

M[Boolean]で、Listをフィルタリングします。とりあえず、Optionを使用した時には、Some(true)を返した時にはその要素が結果Listに残り、Some(false)を返した時には結果Listにはいなくなります。

  println("List(1, 2, 3, 4, 3, 2, 1) filterM some(elm >= 3) => " + {
    List(1, 2, 3, 4, 3, 2, 1) filterM { elm => some(elm >= 3) }
  })
  println("List(1, 2, 3, 4, 3, 2, 1) filterM none => " + {
    List(1, 2, 3, 4, 3, 2, 1) filterM { elm => none[Boolean] }
  })
  println("Nil[Int] filterM some(elm >= 3) => " + {
    nil[Int] filterM { elm => some(elm >= 3) }
  })
  println("Nil[Int] filterM none => " + {
    nil[Int] filterM { elm => none[Boolean] }
  })

実行結果。

List(1, 2, 3, 4, 3, 2, 1) filterM some(elm >= 3) => Some(List(3, 4, 3))
List(1, 2, 3, 4, 3, 2, 1) filterM none => None
Nil[Int] filterM some(elm >= 3) => Some(List())
Nil[Int] filterM none => Some(List())

Nil filterM noneはSomeでNilが返るんですね。

groupByM

M[Boolean]の結果がtrue or falseでグループ分けしたListが返るようです。

  println("List(one, two, three, four, five, six) groupByM some(length > length) => " + {
    List("one", "two", "three", "four", "five", "six") groupByM {
      (a, b) => some(a.length > b.length)
    }
  })
  println("List(one, two, three, four, five, six) groupByM some(length == length) => " + {
    List("one", "two", "three", "four", "five", "six") groupByM {
      (a, b) => some(a.length == b.length)
    }
  })
  println("List(one, two, three, four, five, six) groupByM none => " + {
    List("one", "two", "three", "four", "five", "six") groupByM { (a, b) => none[Boolean] }
  })
  println("Nil[String] groupByM length == length => " + {
    nil[String] groupByM { (a, b) => some(a.length == b.length) }
  })
  println("Nil[String] groupByM length == length => " + {
    nil[String] groupByM { (a, b) => none[Boolean] }
  })

が、実行してみると、けっこうものすごい動きをします。

List(one, two, three, four, five, six) groupByM some(length > length) => Some(List(List(one), List(two), List(three, four, five, six)))
List(one, two, three, four, five, six) groupByM some(length == length) => Some(List(List(one, two), List(three), List(four, five), List(six)))
List(one, two, three, four, five, six) groupByM none => None
Nil[String] groupByM length == length => Some(List())
Nil[String] groupByM length == length => Some(List())

ちょっとprintを仕込んで確認。

  println("List(one, two, three, four, five, six) groupByM some(length > length) => " + {
    List("one", "two", "three", "four", "five", "six") groupByM {
      (a, b) =>
        println("a = [%s], b = [%s]".format(a, b))
        some(a.length > b.length)
    }
  })
  println("List(one, two, three, four, five, six) groupByM some(length == length) => " + {
    List("one", "two", "three", "four", "five", "six") groupByM {
      (a, b) =>
        println("a = [%s], b = [%s]".format(a, b))
        some(a.length == b.length)
    }
  })

a = [one], b = [two]
a = [two], b = [three]
a = [three], b = [four]
a = [three], b = [five]
a = [three], b = [six]
List(one, two, three, four, five, six) groupByM some(length > length) => Some(List(List(one), List(two), List(three, four, five, six)))
a = [one], b = [two]
a = [one], b = [three]
a = [three], b = [four]
a = [four], b = [five]
a = [four], b = [six]
List(one, two, three, four, five, six) groupByM some(length == length) => Some(List(List(one, two), List(three), List(four, five), List(six)))

どうも、引数のタプルの左側は、前の結果がtrueを戻したもので固定されるっぽいですね。falseを返すと、それが次回のタプルの最初の要素になる、と。

inits

これは苦戦しました。Haskellのinitsと同じと思いきや、ちょっと違います。

  println("List(1, 2, 3) inits => " + (List(1, 2, 3): ListW[Int]).inits)
  println("Nil[Int] inits => " + (nil[Int]: ListW[Int]).inits)

実行結果。

List(1, 2, 3) inits => List(List(), List(1, 2, 3), List(1, 2), List(1))
Nil[Int] inits => List(List())

Nilが最初にきて、その後List全体、後ろの要素を1つ削ったList…と続き、残り1つになったところで終了。

ところで、型指定して無理矢理implicit conversionを使用していますが

(List(1, 2, 3): ListW[Int]).inits

これがハマった理由で、普通にinitsメソッドを呼んでもListW#initsは呼び出せません。いつの間にかScala標準ライブラリのListにもinitsメソッドが追加されていて、こちらと衝突してしまいます。

通常のList#initsだと、こうなります。

  println("List(1, 2, 3) standard inits => " + List(1, 2, 3).inits.mkString(", "))
  println("Nil[Int] standard inits => " + nil[Int].inits.mkString(", "))

List(1, 2, 3) standard inits => List(1, 2, 3), List(1, 2), List(1), List()
Nil[Int] standard inits => List()

ただし、返ってくるのはIteratorです。

intercalate

引数で渡したListが、元のListの各要素の間に入り込みます。

  println("List(1, 2, 3) intercalate List(4, 5, 6) => " + {
    List(1, 2, 3) intercalate List(4, 5, 6)
  })
  println("List(1, 2, 3) intercalate Nil => " + {
    List(1, 2, 3) intercalate Nil
  })
  println("Nil[Int] intercalate List(1, 2, 3) => " + {
    nil[Int] intercalate List(1, 2, 3)
  })

実行結果。

List(1, 2, 3) intercalate List(4, 5, 6) => List(1, 4, 5, 6, 2, 4, 5, 6, 3)
List(1, 2, 3) intercalate Nil => List(1, 2, 3)
Nil[Int] intercalate List(1, 2, 3) => List()

intersperse

引数で指定した要素が、元のListの各要素の間に入り込みます。

  println("List(1, 2, 3) intersperse 10 => " + {
    List(1, 2, 3) intersperse 10
  })
  println("List(1) intersperse 10 => " + {
    List(1) intersperse 10
  })
  println("Nil[Int] intersperse 10 => " + {
    nil[Int] intersperse 10
  })

実行結果。

List(1, 2, 3) intersperse 10 => List(1, 10, 2, 10, 3)
List(1) intersperse 10 => List(1)
Nil[Int] intersperse 10 => List()

mapAccumLeft

左からの畳み込みとmapの合わせ技。第2引数がタプルを返す関数となっており、タプルの最初の要素が通常の畳み込みのようになります。結果としてはタプルが返り、最初の要素が畳み込みの結果、2つ目の要素が第2引数の戻り値を並べたListになります。

  println("List(1, 2, 3) mapAccumLeft (5, (c + a, c + a)) => " + {
    List(1, 2, 3) mapAccumLeft (5, (c: Int, a) => (c + a, c + a))
  })
  println("Nil[Int] mapAccumLeft (5, (c + a, c + a)) => " + {
    nil[Int] mapAccumLeft (5, (c: Int, a) => (c + a, c + a))
  })

実行結果。

List(1, 2, 3) mapAccumLeft (5, (c + a, c + a)) => (11,List(6, 8, 11))
Nil[Int] mapAccumLeft (5, (c + a, c + a)) => (5,List())
List(1, 2, 3) mapAccumRight (5, (c + a, c + a)) => (11,List(11, 10, 8))

なので、普通に別々の演算をさせてもいいみたいです。よって、畳み込みとmapの合わせ技。

  println("List(1, 2, 3) mapAccumLeft (5, (c + a, a * 2)) => " + {
    List(1, 2, 3) mapAccumLeft (5, (c: Int, a) => (c + a, a * 2))
  })

List(1, 2, 3) mapAccumLeft (5, (c + a, a * 2)) => (11,List(2, 4, 6))

mapAccumRight

今度は右から行う、畳み込みとmapの合わせ技。

  println("List(1, 2, 3) mapAccumRight (5, (c + a, c + a)) => " + {
    List(1, 2, 3) mapAccumRight (5, (c: Int, a) => (c + a, c + a))
  })
  println("Nil[Int] mapAccumRight (5, (c + a, c + a)) => " + {
    nil[Int] mapAccumRight (5, (c: Int, a) => (c + a, c + a))
  })

実行結果。

List(1, 2, 3) mapAccumRight (5, (c + a, c + a)) => (11,List(11, 10, 8))
Nil[Int] mapAccumRight (5, (c + a, c + a)) => (5,List())

mapAccumLeftとは、返ってきたタプル内のListの要素順が異なります。最初に計算された値が、Listの後ろの方に配置されます。

pairs

List内の各要素でペアを作成します。

  println("List(3, 4, 5, 6) pairs => " + {
    List(3, 4, 5, 6) pairs
  })
  println("Nil[Int] pairs => " + {
    nil[Int] pairs
  })

実行結果。

List(3, 4, 5, 6) pairs => List((3,4), (4,5), (5,6), (3,5), (4,6), (3,6))
Nil[Int] pairs => List()

partitionM

M[Boolean]の結果がtrue or falseで分割したListが返るようです。最初がtrueを返した要素のListで、2つ目がfalseを返した要素のListですね。

  println("List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM some(i % 2 != 0) => " + {
    List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM (i => some(i % 2 != 0))
  })
  println("List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM none(i % 2 != 0) => " + {
    List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM (i => none[Boolean])
  })
  println("List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM some(20 > i) => " + {
    List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM (i => some(20 > i))
  })
  println("Nil[Int] partitionM some(i % 2 != 0) => " + {
    nil[Int] partitionM (i => some(i % 2 != 0))
  })

実行結果。

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM some(i % 2 != 0) => Some((List(1, 3, 5, 7, 9),List(2, 4, 6, 8, 10)))
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM none => None
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) partitionM some(20 > i) => Some((List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),List()))
Nil[Int] partitionM some(i % 2 != 0) => Some((List(),List()))

powerset

これは、ちょっとよく分かりません。

  println("List(1, 2, 3, 4, 5) powerset => " + {
    List(1, 2, 3, 4, 5) powerset
  })
  println("Nil[Int] powerset => " + {
    nil[Int] powerset
  })

実行結果。

List(1, 2, 3, 4, 5) powerset => List(List(1, 2, 3, 4, 5), List(1, 2, 3, 4), List(1, 2, 3, 5), List(1, 2, 3), List(1, 2, 4, 5), List(1, 2, 4), List(1, 2, 5), List(1, 2), List(1, 3, 4, 5), List(1, 3, 4), List(1, 3, 5), List(1, 3), List(1, 4, 5), List(1, 4), List(1, 5), List(1), List(2, 3, 4, 5), List(2, 3, 4), List(2, 3, 5), List(2, 3), List(2, 4, 5), List(2, 4), List(2, 5), List(2), List(3, 4, 5), List(3, 4), List(3, 5), List(3), List(4, 5), List(4), List(5), List())
Nil[Int] powerset => List(List())

これはどうなっているのか？ってことで、powersetの定義を見ると

  def powerset: List[List[A]] = filterM(_ => List(true, false))

となっています。…モナドなので、別にOptionでなくてもListモナドでもよいということですね。が、これが今どういう作用をしているのかはまだ読み解けていません。

spanM

breakMの反対。Listのタプルが返りますが、最初の要素に入るのはM[Boolean]がtrueを返していた間の要素です。

  println("List(1, 2, 3, 4, 5) spanM some(i < 3) => " + {
    List(1, 2, 3, 4, 5) spanM (i => some(i < 3))
  })
  println("Nil[Int] spanM some(i < 3) => " + {
    nil[Int] spanM (i => some(i < 3))
  })

実行結果。

List(1, 2, 3, 4, 5) spanM some(i < 3) => Some((List(1, 2),List(3, 4, 5)))
Nil[Int] spanM some(i < 3) => Some((List(),List()))

そして、実際breakMはspanMを使って定義されています。

  def breakM[M[_] : Monad](p: A => M[Boolean]): M[(List[A], List[A])] =
    spanM(p(_) ∘ (!_))

stripPrefix

引数のList.lengthよりも、後ろのインデックスを持つListが返ります。

  println("List(1, 2, 3, 4, 5) stripPrefix List(1, 2, 3) => " + {
    List(1, 2, 3, 4, 5) stripPrefix List(1, 2, 3)
  })
  println("Nil[Int] stripPrefix List(1, 2, 3) => " + {
    nil[Int] stripPrefix List(1, 2, 3)
  })

実行結果。

List(1, 2, 3, 4, 5) stripPrefix List(1, 2, 3) => Some(List(4, 5))
Nil[Int] stripPrefix List(1, 2, 3) => None

取れなかったら、Noneになります。

tails

initsの逆。今度は、前から削られていきます。

  println("List(1, 2, 3) tails => " + {
    (List(1, 2, 3): ListW[Int]) tails
  })
  println("Nil[Int] tails => " + {
    (nil[Int]: ListW[Int]) tails
  })

実行結果。

List(1, 2, 3) tails => List(List(1, 2, 3), List(2, 3), List(3), List())
Nil[Int] tails => List(List())

最終的には、元のListの最後の要素のみのList、Nilと続きます。

takeUntilM

M[Boolean]がfalseを返している間に集められた要素をListとして返します。trueを返すと、そこで終了。

  println("List(1, 2, 3, 4, 5) takeUntilM some(i > 3) => " + {
    List(1, 2, 3, 4, 5) takeUntilM (i => some(i > 3))
  })
  println("Nil[Int] takeUntilM some(i > 3) => " + {
    nil[Int] takeUntilM (i => some(i > 3))
  })

実行結果。

List(1, 2, 3, 4, 5) takeUntilM some(i > 3) => Some(List(1, 2, 3))
Nil[Int] takeUntilM some(i > 3) => Some(List())

takeWhileM

takeUntilMの逆。M[Boolean]がtrueを返している間の要素を、Listにして返します。

  println("List(1, 2, 3, 4, 5) takeWhileM some(i < 3) => " + {
    List(1, 2, 3, 4, 5) takeWhileM (i => some(i < 3))
  })
  println("Nil[Int] takeWhileM some(i < 3) => " + {
    nil[Int] takeWhileM (i => some(i < 3))
  })

実行結果。

List(1, 2, 3, 4, 5) takeWhileM some(i < 3) => Some(List(1, 2))
Nil[Int] takeWhileM some(i < 3) => Some(List())

toNel

ListをNonEmptyListに変換します。

  println("List(1, 2, 3) toNel => " + List(1, 2, 3).toNel)
  println("Nil[Int] toNel => " + nil[Int].toNel)

実行結果。

List(1, 2, 3) toNel => Some(NonEmptyList(1, 2, 3))
Nil[Int] toNel => None

変換できない（＝Nil）場合は、Noneが返ります。

toZipper

Zipperが返ります。

  println("List(1, 2, 3) toZipper => " + List(1, 2, 3).toZipper)
  println("Nil[Int] toZipper => " + nil[Int].toZipper)

実行結果。

List(1, 2, 3) toZipper => Some(<zipper>)
Nil[Int] toZipper => None

Zipperって？タプルで構成されたListのことじゃないみたい。
ちょっと試してみます。

  val zipper = List(1, 2, 3, 4, 5).toZipper.get
  println("zipper.focus => " + zipper.focus)
  println("zipper.lefts.toList => " + zipper.lefts.toList)
  println("zipper.rights.toList => " + zipper.rights.toList)

getが入っているのは、toZipperの戻り値がOption[Zipper]なので。

zipper.focus => 1
zipper.lefts.toList => List()
zipper.rights.toList => List(2, 3, 4, 5)

focusが現在の値かな？leftsとrightsでStreamが取れます。

moveというメソッドがあるので、移動してみると

  val zipper2 = zipper.move(2).get
  println("zipper2.focus => " + zipper2.focus)
  println("zipper2.lefts.toList => " + zipper2.lefts.toList)
  println("zipper2.rights.toList => " + zipper2.rights.toList)

zipper2.focus => 3
zipper2.lefts.toList => List(2, 1)
zipper2.rights.toList => List(4, 5)

こうなります。現在位置を基点に、leftsがそこから前の要素、rightsがそこから後ろの要素をStreamとして見せている、ってことみたいですね。よって、leftsは逆順になっています。

zipperEnd

最後の要素から作成したZipperが返ります。

  println("List(1, 2, 3) zipperEnd => " + List(1, 2, 3).zipperEnd)
  println("Nil[Int] zipperEnd => " + nil[Int].zipperEnd)

実行結果。

List(1, 2, 3) zipperEnd => Some(<zipper>)
Nil[Int] zipperEnd => None

最後の要素から作成したZipperとは？要は、こういうことです。

  val zipperEnd = List(1, 2, 3, 4, 5).zipperEnd.get
  println("zipperEnd.focus => " + zipperEnd.focus)
  println("zipperEnd.lefts.toList => " + zipperEnd.lefts.toList)
  println("zipperEnd.rights.toList => " + zipperEnd.rights.toList)

zipperEnd.focus => 5
zipperEnd.lefts.toList => List(4, 3, 2, 1)
zipperEnd.rights.toList => List()

う〜ん、長かったです。モナドを使用するメソッドの挙動が、よく分かっていませんね。