Haskell 勉強メモ6

haskell scala

再帰

関数型言語では再帰はよく出てくる。

最大値を求める関数を考えてみる。命令的に考えると、現在の最大値を保持する変数を用意し、リストの全ての要素についてループして、変数を更新していく形になる。Scalaで書いてみると

def maximum(list: List[Int]): Int = {
  var max = list.head
  list.foreach { v =>
    if (v > max) max = v
  }
  max
}

となる。再帰的に書く場合最初に基底部（解を明示的に定義しなければならないケース）を定義しなければならない。単一要素のリストに対する最大値は、その唯一の要素と同じ値である。それ以上の場合は、リストの先頭要素と残りのリストの最大値でどちらが大きいかを見る。Scalaで書いてみる。

def maximum(list: List[Int]): Int = {
  def max(a: Int, b: Int): Int = if (a >= b) a else b
  list match {
    case Nil => throw new IllegalArgumentException
    case ::(head, next) if list.size == 1 => head
    case ::(head, next) => max(head, maximum(next))
  }
}

要素が1つのみの表現がわからなかったので、ガードでかいた。

Haskellでは

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximun of empty list!"
maximum' [x] = x
maximum' (x : xs) = max x (maximum' xs)

*Main> maximum' [1, 3, 5, 0, 13, 11, 12]
13

replicate

Int と値をとり、その値を指定された数だけ繰り返したリストを返す。

Haskell には元々ある。

*Main> replicate 3 5
[5,5,5]

基底部を考える。0 以下の回数だけ複製することはできないので、この際は空のリストを返す。

replicate' :: Int -> a -> [a]
replicate' n x
  | n <= 0 = []
  | otherwise = x : replicate' (n - 1) x

Scalaで書く場合

def replicate[T](n: Int)(x: T): List[T] =
  n match {
    case k if k <= 0 => Nil
    case k           => x +: replicate(n - 1)(x)
  }

replicate(3)(5) // val res2: List[Int] = List(5, 5, 5)

Scala側はカリー化する必要はあまりないが、Haskell と合わせている。

take

takeは指定されたリストから指定された数を返す。

take' :: Int -> [a] -> [a]
take' n _
  | n <= 0 = []
take' _ [] = []
take' n (x : xs) = x : take' (n -1) xs

*Main> take' 3 [1,2,3,4,5]
[1,2,3]

Scalaでの記述

def take[T](n: Int)(xs: List[T]): List[T] =
  (n, xs) match {
    case (k, _) if k <= 0    => Nil
    case (_, Nil)            => Nil
    case (k, ::(head, next)) => head +: take(k-1)(next)
  }

take(2)(List(1,2,3,4,5)) // val res3: List[Int] = List(1, 2)

Scalaのリストメソッドには、takeはあらかじめ実装されているので実用上はわざわざ作る必要はない。

override def take(n: Int): List[A] = if (isEmpty || n <= 0) Nil else {
    val h = new ::(head, Nil)
    var t = h
    var rest = tail
    var i = 1
    while ({if (rest.isEmpty) return this; i < n}) {
      i += 1
      val nx = new ::(rest.head, Nil)
      t.next = nx
      t = nx
      rest = rest.tail
    }
    releaseFence()
    h
  }

手続き的な実装にはなっているが。

reverse

関数をリストに取り、逆順のリストを返す

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x : xs) = reverse' xs ++ [x]

Scala だと

def reverse[T](xs: List[T]): List[T] = xs match {
  case Nil => Nil
  case ::(head, next) => reverse(next) :+ head
}

reverse(List(1,2,3,4,5)) // val res3: List[Int] = List(5, 4, 3, 2, 1)

repeat

受け取った要素から無限リストを作る関数。Haskellは基本遅延評価だから、無限リストでも途中で切るようにとれば問題ない。

*Main> take 3 (repeat 5)
[5,5,5]

再帰的実装は

repeat' :: a -> [a]
repeat' x = x : repeat' x

*Main> take 3 (repeat' 3)
[3,3,3]

Scalaの通常のListは遅延評価ではないから、真似はできないか調べたら LazyList っていうのがあるのを知った。

val lazyList: LazyList[Int] = LazyList.continually(1).take(15)
var count = 0
lazyList.foreach { v => count += v}
println(count) // 15

API ドキュメントに記載されているサンプルが分かりやすい。

val fibs: LazyList[Int] = {
  0 #:: 1 #:: fibs.zip(fibs.tail).map { n =>
    println(s"Adding ${n._1} and ${n._2}")
    n._1 + n._2
  }
}
fibs.take(5).foreach(println)
// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3

fibs.take(6).foreach(println)
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5

アクセスされて初めて評価されていることが分かる。

zip

2つのリストを引数にとり、これらを綴じ合わせて返す。

Prelude> zip [1,2] ['a', 'b', 'c']
[(1,'a'),(2,'b')]

Scala

List(1,2,3).zip(List("a", "b")) // val res9: List[(Int, String)] = List((1,a), (2,b))

実装。どちらか一方が空のリストの時は、空のリストを返す。

どちらの先頭要素もあれば、先頭要素をとったタプルを作り、再帰する

zip' :: [a] -> [b] -> [(a, b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x, y) : zip' xs ys

Scalaで書くと

def zip[A, B](a: List[A])(b: List[B]): List[(A, B)] =
  (a, b) match {
    case (_, Nil)               => Nil
    case (Nil, _)               => Nil
    case (::(x, xs), ::(y, ys)) => (x, y) +: zip(xs)(ys)
  }

zip(List(1, 2, 3))(List("a", "b")) // val res11: List[(Int, String)] = List((1,a), (2,b))

elem

値とリストを受け取り、その値がリストに含まれるか調べる関数

*Main> 1 `elem` [2,3,4]
False

Scalaだと contains にあたるかなと。

List(2,3,4).contains(1)

Haskell 再帰での実装。基底部は空のリストを受け取った時のFalse。リストに要素がある場合は、先頭と値を比較して一致しなければ、残りの要素に対して再帰する。

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x = True
    | otherwise = a `elem'` xs

Scalaでの実装

@tailrec
def elem[A](a: A)(list: List[A]): Boolean = (a, list) match {
  case (_, Nil) => false
  case (a, ::(x, _)) if a == x => true
  case (a, ::(_, xs)) => elem(a)(xs)
}

elem(1)(List(2,3,4)) // val res13: Boolean = false
elem(1)(List(2,1,3)) // val res14: Boolean = true