CとHaskellの比較@二分木

Haskell 30分プログラム

30分プログラム、Haskellで二分木。

  1. 院試の過去問で、C言語での二分木が出題されている
  2. 正解を確かめるために、そのソースを写した
  3. 木の構造が見たいけど、Cでそれを書くのは面倒だな
  4. Haskellでderiving Showしよ

というわけで、同じプログラムのC版とHaskell版ができたので、それでお茶を濁しておく。

まずは、オリジナルのソースコード。
もとの問題がこれだったんだから、グローバル変数が汚ないとか言われても困りますよ。

#include <stdio.h>
#include <stdlib.h>

#define N 5
int data[N] = { 5, 10, 3, 12, 8 };

typedef struct tree{
  int val;
  struct tree *left;
  struct tree *right;
} TREE;

TREE *insert(TREE *t, int x){
  if(t == NULL){
    t = malloc(sizeof(TREE));
    t->val = x;
    t->left = NULL;
    t->right = NULL;
  }else if(x > t->val){
    t->left  = insert(t->left,x);
  }else{
    t->right = insert(t->right,x);
  }
  return t;
}

void traverse(TREE *t){
  if(t != NULL){
    traverse(t->right);
    printf("%d\n",t->val);
    traverse(t->left);
  }
}

int main(){
  TREE *t;
  int i;

  t = NULL;
  i = 0;
  while(i < N){
    t = insert(t,data[i]);
    i = i+1;
  }
  traverse(t);
  return 0;
}

で、これのHaskell版。

data Tree = Leaf | Branch Int Tree Tree deriving Show

insert :: Tree -> Int -> Tree
insert Leaf x = Branch x Leaf Leaf
insert (Branch value left right) x = 
    if x > value 
      then Branch value (insert left x) right
      else Branch value left (insert right x)

traverse Leaf = putStr ""
traverse (Branch value left right) = do traverse left
                                        putStrLn $ show value
                                        traverse right

main = let t = foldl insert Leaf [5,10,3,12,8] 
       in traverse t

ちなみに見たかった構造は、これ。

Main> t = scanl insert Leaf [5,10,3,12,8] 

Main> mapM_ (putStrLn.show) t
Leaf
Branch 5 Leaf Leaf
Branch 5 (Branch 10 Leaf Leaf) Leaf
Branch 5 (Branch 10 Leaf Leaf) (Branch 3 Leaf Leaf)
Branch 5 (Branch 10 (Branch 12 Leaf Leaf) Leaf) (Branch 3 Leaf Leaf)
Branch 5 (Branch 10 (Branch 12 Leaf Leaf) (Branch 8 Leaf Leaf)) (Branch 3 Leaf Leaf)