KotlinとOCamlでバイナリーツリーの比較

KotlinとOCamlを勉強した

Kotlinが関数型っぽく書けるようなので比較してみる。

Kotlinではifもwhen(パターンマッチング)も式であり、値を返す。
つまりif,whenは関数である。

なので、Kotlinは基本は手続き型言語だが、書き方によってはプログラムを一つの関数として書ける。

OCaml（関数型言語）の場合

# バイナリーツリー（２分木）の定義

type 'a binary_tree =
  Empty
| Node of 'a * 'a binary_tree * 'a binary_tree;;

# 要素のfind関数: find(x,tree): 返り値 boolean

let rec find x tree =
  match tree with
    Empty -> false
  | Node(y, left, right) ->
      if x = y then true else
      if x < y then find x left else find x right;;

# Tree作成

let tree = Node(4, Node(2, Node(1, Empty, Empty), Node(3, Empty, Empty)), Empty);;

# find実行
find 1 tree;; // -> true

kotlinの場合も同じように書ける？

Node定義

• classとして定義すればいいっぽい。クラスを再帰的に定義できる。

# node
class Node(var value: Int, var left: Node? = null, var right: Node? = null)

# binary_tree作成
val binary_tree = Node(6, Node(3, Node(2), Node(5)), Node(8, Node(7), Node(9)))

find関数

• 手続き的に書いてもいいが、ifとwhenを関数として値を返させるように使える。

fun find(tree: Node?, x: Int): Boolean =
        when (tree) {
            null -> false
            is Node -> {
                if (tree.value == x) {
                    true
                } else if (tree.value < x) {
                    find(tree.right, x)
                } else {
                    find(tree.left, x)
                }
            }
            else -> throw Error("error")
        }

Tree作成とfind実行

fun main(args: Array<String>) {
    val tree = Node(6, Node(3, Node(2), Node(5)), Node(8, Node(7), Node(9)))

    println("find 6: ${find(tree,6)}") 
}


　　　　　　　// -> "find 6: true"が出力される

OCamlとKotlinで、見た目かなり似てるように書けているような気がしました。

（終）