2021-04-18

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

2021-04-11

Haskell 勉強メモ5

haskell scala

let式

let 式は変数を束縛する。 let 式自身も式。式であるとは、「値を持つ」ということ。

円柱の表面積を求める。

cylinder :: Double -> Double -> Double
cylinder r h =
  let sideArea = 2 * pi * r * h
      topArea = pi * r ^ 2
   in sideArea + 2 * topArea

*Main> cylinder 4 10
351.85837720205683

let は式であるので、コードの中のどんなところでも使える。

*Main> 4 * (let a = 9 in a + 1) + 2
42

-- ローカルスコープに関数を作る
*Main> [let square x = x * x in (square 5, square 3, square 2)]
[(25,9,4)]

-- タプル要素を分解してそれぞれの名前に束縛する
*Main> (let (a, b, c) = (1, 2, 3) in a + b + c) * 100
600

case 式

パターンマッチで使う。

head' :: [a] -> a
head' xs = case xs of
  [] -> error "No head for empty lists"
  (x : _) -> x

*Main> head' []
*** Exception: No head for empty lists
CallStack (from HasCallStack):
  error, called at baby.hs:3:9 in main:Main
*Main> head' [1, 2]
1
*Main>

case 式の構文は下記

 case expression of pattern -> result
                pattern -> result
                pattern -> result

式に合致した最初のパターンが使われる。

case 式はどこでも使える。

describeList :: [a] -> String
describeList ls =
  "The list is "
    ++ case ls of
      [] -> "empty"
      [x] -> "a singleton list"
      xs -> "a longer list"

*Main> describeList []
"The list is empty"
*Main> describeList [1, 2]
"The list is a longer list"
*Main> describeList [1]
"The list is a singleton list"

2021-04-04

Haskell 勉強メモ4

未分類

関数を書くための構文

パターンマッチ

Scala でもたくさん使うパターンマッチ。Haskell版も見てく。

渡された数が7かどうかを判別する関数。

Haskell版

lucky :: Int -> String
lucky 7 = "LUCKY NUMBER SEVEN!"
lucky x = "Sorry, you're out of luck, pal!"

*Main> lucky 8
"Sorry, you're out of luck, pal!"
*Main> lucky 7
"LUCKY NUMBER SEVEN!"

lucky を呼ぶと、パターンが上から下の順で試される。

Scala版

def lucky(n: Int): String = n match {
  case 7 => "LUCKY NUMBER SEVEN!"
  case _ => "Sorry, you're out of luck, pal!"
}

lucky(8) // val res11: String = Sorry, you're out of luck, pal!
lucky(7) // val res12: String = LUCKY NUMBER SEVEN!

階乗計算するプログラムをパターンマッチを使って、再帰的に書く。

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

Scalaの場合

def factorial(n: Int): Int = n match {
  case 0 => 1
  case k => k * factorial(k-1)
}

タプルのパターンマッチもできる。

２次元ベクトルの足し算。

addVectors :: (Double, Double) -> (Double, Double) -> (Double, Double)
addVectors a b = (fst a + fst b, snd a + snd b) -- これだと読みづらい。
addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2) -- こう書くと直感的

リスト内包表記でもパターンマッチが使える。

*Main> let xs = [(1,3),(4,3),(2,4),(5,3),(5,6),(3,1)]
*Main> [a + b | (a, b) <- xs]
[4,7,6,8,11,4]

-- マッチしない要素は結果に反映されない。
*Main> [x*100 + 3 | (x, 3) <- xs]
[103,403,503]

val list = Seq((1,3),(4,3),(2,4),(5,3),(5,6),(3,1))
for ((a, b) <- list) yield a + b // val res13: Seq[Int] = List(4, 7, 6, 8, 11, 4)
for ((x, 3) <- list) yield x*100 + 3 // val res14: Seq[Int] = List(103, 403, 503)

リストもパターンマッチで使える。空のリスト [] または、: を含むパターンと合致させることができる。x:xs というパターンは、リストの先頭要素を x に束縛し、リストの残りを xs に束縛する。

head' :: [a] -> a 
head' [] = error "Can't call head on an empty list, dummy!"
head' (x: _) = x

*Main> head' []
*** Exception: Can't call head on an empty list, dummy!
CallStack (from HasCallStack):
  error, called at baby.hs:40:12 in main:Main
*Main> head' [2,3,4]
2

Scalaのパターンマッチの場合は下記。

def head[T](list: List[T]): T = list match {
  case x::_ => x
  case Nil => throw new IllegalArgumentException
}

head(List(2,3,4)) // val res0: Int = 2
head(List()) // java.lang.IllegalArgumentException

asパターン

Haskellには as パターン という特殊なパターンがある。値をパターンに分解しつつ、パターンマッチの対象になった値自体も参照したいときに使う。@ を使うことで、元のリスト全体にアクセスすることができる。

firstLetter :: String -> String
firstLetter "" = "Empty string whoops!"
firstLetter all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

*Main> firstLetter "Dracula"
"The first letter of Dracula is D"

知らなかったが Scala でも同じことができるらしい。参考

上と似たことをScalaでやると。

def firstLetter(letters: List[Char]): String = {
  letters match {
    case Nil => "Empty string whoops!"
    case all @ (x::xs) => s"The first letter of ${all} is $x"
  }
}

firstLetter("Dracula".toList) // val res3: String = The first letter of List(D, r, a, c, u, l, a) is D

@ を使うことで、元の要素にアクセスできていることが分かる。Scalaの場合は、元の要素をそのまま使えばいいんじゃとか思うけど、何か違うのだろうか。。？

ガード

引数の値が満たす性質で場合分けするとき。

bmiTell :: Double -> String
bmiTell bmi
  | bmi <= 18.5 = "underweight."
  | bmi <= 25.0 = "normal"
  | bmi <= 30.0 = "fat"
  | otherwise = "Are you Whale?"

参考本のサンプルはもっと毒々しかったけど、書くの面倒だった。bmi の値で場合分けしている。

Scalaで書く場合は

def bmiTell(bmi: Double): String =
  bmi match {
    case v if v <= 18.5 => "underweight"
    case v if v <= 25.0 => "normal"
    case v if v <= 30.0 => "fat"
    case v              => "Are you whale?"
  }

複数引数でも可能。

bmiTell :: Double -> Double -> String
bmiTell weight height
  | weight / height ^ 2 <= 18.5 = "underweight."
  | weight / height ^ 2 <= 25.0 = "normal"
  | weight / height ^ 2 <= 30.0 = "fat"
  | otherwise = "Are you Whale?"

where

命令型のプログラミング言語なら、同じ値を何度を計算するのを避けるため、変数に格納するやることが一般的。Haskellでは、where キーワードをつかて計算の中間結果に名前をつける。さっきの bmiTell だと where /height ^ 2 を何度も書く&再評価するのは無駄が多い。下記のように修正する。

bmiTell :: Double -> Double -> String
bmiTell weight height
  | bmi <= 18.5 = "underweight."
  | bmi <= 25.0 = "normal"
  | bmi <= 30.0 = "fat"
  | otherwise = "Are you Whale?"
  where
    bmi = weight / height ^ 2

where のなかでパターンマッチを使うこともできる。

initials :: String -> String -> String
initials firstname lastname = [f] ++ " " ++ [l] ++ "."
  where
    (f : _) = firstname
    (l : _) = lastname

where ブロック内では、定数だけでなく関数も定義できる。

calcBmis :: [(Double, Double)] -> [Double]
calcBmis xs = [bmi w h | (w, h) <- xs]
  where
    bmi weight height = weight / height ^ 2

2021-03-28

Haskell 勉強メモ3

未分類

型変数

Haskellの head 関数の型を見てみる。

*Main> :t head
head :: [a] -> a

この a が型変数と呼ばれる。型変数によって関数を複数の型に対して動作するようにできる。型変数を用いた関数は多相的関数と呼ばれる。

どのような型でも良いという性質のことを多相性(polymorphism)と呼ぶ。型変数を含むような型のことを多相型 と呼ぶ。

型クラス

型クラス (type class) とは、ある型が何らかの性質を持つことを示すインターフェースのこと。型クラスは関数の集まりを定める。型クラスに属する関数のことをその型クラスのメソッドと呼ぶことがある。

等価性を定義する型クラスの例

*Main> :t (==)
(==) :: Eq a => a -> a -> Bool

これは、等価性関数が「同じ型の任意の2つの引数を取り、Boolを返す」関数であることを意味する。

シンボル => よりも前にあるものは型クラス制約と呼ばれ、「引数の2つの値のかたは Eq クラスのインスタンス出なければならない」ことを示す。

型クラスの例

`Eq` 型クラス

等価性をテストできる型に使われる。関数の型変数に Eq クラスの制約がついていたら、その関数の定義のどこかで、== か /= が使われていることを示す。

`Ord` 型クラス

順序を付けられる型のための型クラス。

*Main> :t (>)
(>) :: Ord a => a -> a -> Bool

引数を2つとり、それらが関係を満たすかどうかを教えてくれる Bool を返す。

compare 関数は Ord のインスタンスの型の引数を2つとり、Ordering を返す。Ordering は GT, LT, EQ のいずれかをとる。

*Main> :t compare
compare :: Ord a => a -> a -> Ordering
*Main> "Abrakadabra" < "Zebra"
True
*Main> "Abrakadabra" `compare` "Zebra"
LT
*Main> 5 >= 2
True
*Main> 5 `compare` 3
GT
*Main> 'b' > 'a'
True
*Main>

`Show` 型クラス

ある値は、その型が Show 型クラスのインスタンスになっていれば、文字列として表現できる。この型クラスの操作でよく使われるのが show で、これは指定した値を文字列として表示する関数。※ print 文みたいなものかな？

*Main> show 3
"3"
*Main> show 5.334
"5.334"
*Main> show True
"True"

`Read` 型クラス

Show 型と対をなす型クラス。read 関数は文字列を受け取り、Read のインスタンスの方を返す。

*Main> :t read
read :: Read a => String -> a

*Main> read "True" || False
True
*Main> read "8.2" + 3.8
12.0
*Main> read "5" - 2
3
*Main> read "[1,2,3,4]" ++ [3]
[1,2,3,4,3]

*Main> read "5" -- Floatなのか、Intなのか、それ以外なのか判断できないためエラー
*** Exception: Prelude.read: no parse
*Main> read "5" :: Float -- 型を明示する必要がある。
5.0
*Main> read "5" :: Int 
5

`Enum` 型クラス

列挙型。値をレンジの中で使える。

*Main> ['a' .. 'e']
"abcde"
*Main> [LT .. GT]
[LT,EQ,GT]
*Main> [3 .. 5]
[3,4,5]
*Main> succ 'B'
'C'

`Bounded` 型クラス

上限と下限を持つ。それぞれ、 minBound と maxBound 関数で調べることができる。

*Main> minBound :: Int
-9223372036854775808
*Main> maxBound :: Int
9223372036854775807
*Main> maxBound :: Char
'\1114111'
*Main> maxBound :: Bool
True
*Main> minBound :: Bool
False

Num型クラス

数の型クラス

*Main> :t 20
20 :: Num p => p

Floating 型クラス

Float と Double

Integral 型クラス

整数（全体）のみが含まれる数の型クラス。

2021-03-21

Haskell 勉強メモ2

haskell scala

明示的な型宣言

Haskellの型宣言は2行で書く模様。こういう書き方は初めて。

removeNonUppercase :: [Char] -> [Char]
removeNonUppercase st = [c | c <- st, c `elem` ['A' .. 'Z']]

*Main> removeNonUppercase("HelloWorld")
"HW"

addThree :: Int -> Int -> Int -> Int
addThree x y z = x + y + z

*Main> addThree 1 2 3
6

Scalaだとこうかな。

def removeNonUppercase(st: Seq[Char]): Seq[Char] = {
  for (c <- st if ('A' to 'Z').contains(c)) yield c
}

removeNonUppercase("HelloWorld") // val res6: Seq[Char] = Vector(H, W)

def addThree(x: Int)(y: Int)(z: Int): Int = x + y + z

addThree(1)(2)(3) // val res7: Int = 6

一般的なHaskellの型

他の言語同様、Int 型がありマシンのワードサイズによって異なる模様。64ビットCPUの場合Intの範囲は -2^63〜2^63-1 なのでScalaだとLong型相当。他にInteger 型があって、これは有界ではなく大きな数値が扱える。BigInt的なものか。

factorial :: Integer -> Integer
factorial n = product [1 .. n]

*Main> factorial 50
30414093201713378043612608166064768844377641568960512000000000000

def factorial(n: BigInt) =  (BigInt(1) to n).foldLeft(BigInt(1)){ (a, b) => a * b}
factorial(BigInt(50)) // val res8: BigInt = 30414093201713378043612608166064768844377641568960512000000000000

FloatとDouble。Floatは単精度浮動小数点数、Doubleは倍精度浮動小数点型。

円の面積を求める関数で試してみる。

circumference :: Float -> Float
circumference r = 2 * pi * r

*Main> circumference 4.0
25.132742

circumference' :: Double -> Double 
circumference' r = 2 * pi * r

*Main> circumference' 4.0
25.132741228718345

Scala版

def circumferenceF(r: Float): Float = 2.0f * math.Pi.toFloat * r

def circumferenceD(r: Double): Double = 2.0 * math.Pi * r

circumferenceF(4.0f) // val res9: Float = 25.132742
circumferenceD(4.0) // val res10: Double = 25.132741228718345

他にも

真偽値 Bool (True, False)
Char 型（Unicode文字を表し、シングルクォート ' で括って表記する）
タブルも型。空のタプル () も型の一つで、ただ一つのあたい () のみをもつ※これはユニットと呼ばれる。

2021-03-14

Haskell 勉強メモ 1

haskell scala

関数型プログラミングをちゃんとやろうと思って「すごいHaskellたのしく学ぼう！」を買って読み始めた。その勉強メモ。自分のメイン言語はScalaなので、気になったところを比較しながら見ていく。

内包表記

Haskellのリスト内包表記。集合の内包的記法の概念。$latex \{2\cdot x | x \in N, x \le 10 \}$ を書いてみる。

Prelude> [x*2 | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]

Scalaで似たようなものを書く場合は、for 内包表記を使う。

scala> for (i <- 1 to 10) yield i * 2
val res1: IndexedSeq[Int] = Vector(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

もう少し複雑な条件で。

2倍したもののうち、12以上のものからなるリストが欲しい場合

Prelude> [x*2 | x <- [1..10], x*2 >= 12]
[12,14,16,18,20]

scala> for (i <- 1 to 10 if i*2 >= 12) yield i*2
val res3: IndexedSeq[Int] = Vector(12, 14, 16, 18, 20)

10以上の全ての奇数を"BANG!"に置き換え、10より小さい全ての奇数を"BOOM!"に置き換える内包表記。

boomBangs xs = [ if x < 10 then "BOOM!" else "BANG!" | x <- xs, odd x]

// boomBangs [7..13]
// ["BOOM!","BOOM!","BANG!","BANG!"]

def boomBangs(xs: Seq[Int]): Seq[String] = {
  for (x <- xs if x % 2 == 1) yield {
    if (x < 10) "BOOM" else "BANG!"
  }
}

// boomBangs(7 to 13)
// val res1: Seq[String] = Vector(BOOM, BOOM, BANG!, BANG!)

複数の述語を含める場合。Haskellは間まで区切る。and条件

*Main> [ x | x <- [10..20], x /= 13, x /= 15, x /= 19]
[10,11,12,14,16,17,18,20]

Scalaは if の真偽値が想定になるようにしてあげればいい

for (x <- 10 to 20 if x != 13 && x != 15 && x !=19) yield x
val res2: IndexedSeq[Int] = Vector(10, 11, 12, 14, 16, 17, 18, 20)

複数のリストから値を取り出す

*Main> [ x+y | x <- [1,2,3], y <- [10,100,1000] ]
[11,101,1001,12,102,1002,13,103,1003]

for (
  x <- 1 to 3;
  y <- Seq(10,100,1000)
) yield x + y

val res3: IndexedSeq[Int] = Vector(11, 101, 1001, 12, 102, 1002, 13, 103, 1003)

述語論理を追加する

*Main> [ x*y | x <- [2,5,10], y <- [8,10,11], x*y > 50]
[55,80,100,110]

for (
  x <- Seq(2,5,10);
  y <- Seq(8,10,11)
  if (x*y > 50)
) yield x*y

直角三角形を見つける

3辺の長さ全て整数
各辺の長さは10以下
周囲の長さは24に等しい

Haskellで書く

// aは斜辺cを超えないかつ、bはaを超えない
triples = [(a, b, c) | c <- [1 .. 10], a <- [1 .. c], b <- [1 .. a], a ^ 2 + b ^ 2 == c ^ 2, a + b + c == 24]
// [(8,6,10)]

Scalaで書く。Scalaだと ^ みたなメソッドはないから、implicit class でちょろっと作って使ってみる

implicit class MyInt(value: Int) {
  def **(n: Int):Int = {
    n match {
      case 0 => 1
      case k => value * **(k-1)
    }
  }
}

val x:Int = 2 ** 5 // 32

for (
  c <- 1 to 10;
  a <- 1 to c;
  b <- 1 to a
  if a ** 2 + b ** 2 == c ** 2
  if a + b + c == 24
) yield (a,b,c)

val res5: IndexedSeq[(Int, Int, Int)] = Vector((8,6,10))

全体的にHaskellの方が数学チックな表現ができるなって印象。Scalaと対比でみることで、Scalaの理解が進みそう。

2021-02-21

階層構造のデータから特定のプロパティを抽出して、フラットにする

scala 再帰

json のような階層構造を持つデータから特定のプロパティを再帰的に探索して、平坦なリストにしたものを取得したい場面に出会ったのでメモする。

データ構造

case class Tree(
    value: Int,
    children: List[Tree]
)

木構造？というか、自身のリストを持つようなデータ構造。

実装

再帰でなんとかする

case class Tree(value: Int, children: List[Tree]) {
  val values: List[Int] = {
    @tailrec
    def loop(children: List[Tree], vs: List[Int]): List[Int] = {
      children match {
        case Nil => vs
        case ::(head, next) => loop(next ++ head.children, vs appended  head.value)
      }
    }
    loop(children, List(value))
  }
}

実行結果

val tree = {
  Tree(
    1,
    List(
      Tree(2, List.empty),
      Tree(3, List.empty),
      Tree(4, List(
        Tree(5, List.empty),
        Tree(6, List.empty),
        Tree(7, List(
          Tree(8, List(
            Tree(9, List(
              Tree(12, List(
                Tree(13, List.empty)
              ))
            ))
          )),
          Tree(10, List(
            Tree(11, List.empty)
          ))
        ))
      ))
    )
  )
}

println(tree.values) // List(1, 2, 3, 4, 5, 6, 7, 8, 10, 9, 11, 12, 13)</pre>

うん。できてそう。

ちゃんとテストしたわけではない。

問題点

自身のプロパティにアクセスするような実装のため、ほぼ同じ処理なのに共通化しづらいのが難点。再帰的にとってくるような処理をあっちこっちでやると同じ処理が散らばる。

replicate

take

reverse

repeat

zip

elem

let式

case 式

パターンマッチ

asパターン

ガード

where

型変数

型クラス

型クラスの例

Eq 型クラス

Ord 型クラス

Show 型クラス

Read 型クラス

Enum 型クラス

Bounded 型クラス

Num型クラス

Floating 型クラス

Integral 型クラス

明示的な型宣言

一般的なHaskellの型

内包表記

データ構造

実装

実行結果

問題点

`Eq` 型クラス

`Ord` 型クラス

`Show` 型クラス

`Read` 型クラス

`Enum` 型クラス

`Bounded` 型クラス