Haskell Quiz No.16

難易度: λλ

以下のような二分木の定義があります。

以下の操作を定義してみましょう!

(1) 部分木を左右反転させた木を返す関数

mirror 関数適用前mirror 関数適用後

左の木に mirror 関数を適用すると、右の木を返します。

(2) 木の高さを計算する関数

depth

depth 関数で上記の木の高さを計算すると 3 になります。

(3) 木が平衡かチェックする関数

  • 平衡の定義: 左右の部分木の高さが高々1しか違わない

isBalanced

上記の木は 平衡 です。

さらに FunctorFoldable のインスタンスを定義してみましょう!(ここでは fmapfoldMap を定義することにします。)

答えは次回。

※ 図の作成には mermaidというツールを使っています。

参考

  • Programming in Haskell (14.2 Foldables and friends)
  • 関数プログラミング入門 Haskell で学ぶ原理と技法 (8.3.2 木による表現)
  • CIS 623

はじめに

前回の問題と答えは以下の通りです。

問題

難易度: λ

葉にだけ値を持つような二分木を定義してみてください!

図で書くとこんな感じです。

木の図

こたえ

解説

この定義を使って図の木を作るとこんな感じになります。

where を使わない場合はこんな感じです。

以上です。