「ANSI Common Lisp」4章練習問題 - Haskell版

1. 正方の配列(大きさが(n n)の配列)を引数としてそれを90度、時計回りに回転させる関数を定義せよ。

Lispの時に手抜きした分、めちゃくちゃ時間かかりました。。

-- 数列を右回りに90度回転
quarterTurn :: [[a]] -> [[a]]
quarterTurn det = foldl makeDet [] det

-- 受け取ったリストを右回りに90度回転
rotate :: [a] -> [[a]]
rotate xs = map (\n -> [n]) xs

-- 受け取ったリストを回転させた数列に追加
makeDet :: [[a]] -> [a] -> [[a]]
makeDet [] ys = rotate ys
makeDet xs ys = map (\t -> fst t : snd t) $ myzip ys xs

-- リストとリストのリストを受け取ってタプルに変換
myzip :: [a] -> [[b]] -> [(a, [b])]
myzip [] [] = []
myzip (x:xs) (y:ys) = (x, y) : myzip xs ys

-- テストドライバ
main = do print $ quarterTurn ["ab","cd"]
          print $ quarterTurn ["abc","def"]

結果はこう。

["ca","db"]
["da","eb","fc"]

2. reduceを使って以下のものを定義せよ

(a) copy-list

myCopyList xs = foldr (:) [] xs

main = do print [1..3]
          print $ myCopyList [1..3]

結果はこう。

[1,2,3]
[1,2,3]

(b) reverse(リストが対象)

myCopyList xs = foldl (\a b -> b : a) [] xs

main = do print $ reverse [1..3]
          print $ myCopyList [1..3]

結果はこう。

[3,2,1]
[3,2,1]

3. それぞれのノードがデータをもち、3つまでの子がとれるようなツリーを表現するストラクチャを定義した上で、以下の関数を定義せよ。

とりあえずストラクチャを定義。

-- 3つのノードを持つ木構造を定義
data MyNode d l c r = Empty | MyNode d (MyNode d l c r) (MyNode d l c r) (MyNode
 d l c r)

-- データを定義
-- 1 --- 2
--    |
--    -- 3 --- 5
--    |     |
--    |     -- 6
--    |     |
--    |     -- 7
--    | 
--    -- 4
childNode7 = MyNode 7 Empty Empty Empty
childNode6 = MyNode 6 Empty Empty Empty
childNode5 = MyNode 5 Empty Empty Empty
childNode4 = MyNode 4 Empty Empty Empty
childNode3 = MyNode 3 childNode5 childNode6 childNode7
childNode2 = MyNode 2 Empty Empty Empty
rootNode = MyNode 1 childNode2 childNode3 childNode4

main = print $ showMyNode rootNode

-- MyNodeを表示する関数
showMyNode :: (Show d) => (MyNode d l c r) -> String
showMyNode Empty = "Empty"
showMyNode (MyNode d l c r) = "(" ++ (show d) ++ "," ++ (showMyNode l) ++ "," ++
 (showMyNode c) ++ "," ++ (showMyNode r) ++ ")"

-- MyNodeから左ノードを取り出す
leftNode :: (MyNode d l c r) -> (MyNode d l c r)
leftNode (MyNode d l c r) = l

-- MyNodeから中央ノードを取り出す
centerNode :: (MyNode d l c r) -> (MyNode d l c r)
centerNode (MyNode d l c r) = c

-- MyNodeから右ノードを取り出す
rightNode :: (MyNode d l c r) -> (MyNode d l c r)
rightNode (MyNode d l c r) = r

結果はこう。

"(1,(2,Empty,Empty,Empty),(3,(5,Empty,Empty,Empty),(6,Empty,Empty,Empty),(7,Empty,Empty,Empty)),(4,Empty,Empty,Empty))"

見づらいがまあ出来てそう。
Haskellのデータ定義とかすっ飛ばしたせいか、さっぱり理解してない。
こんなんでいいのだろうか。。

(a) このようなツリーをコピーする関数(コピーのノードがオリジナルのノードとeqlにならないように)

-- MyNodeをコピーする
copyMyNode :: (MyNode d l c r) -> (MyNode d l c r)
copyMyNode Empty = Empty
copyMyNode (MyNode d l c r) = MyNode d (copyMyNode l) (copyMyNode c) (copyMyNode r)

main = do print $ showMyNode rootNode
          print $ showMyNode $ copyMyNode rootNode

結果はこう。

"(1,(2,Empty,Empty,Empty),(3,(5,Empty,Empty,Empty),(6,Empty,Empty,Empty),(7,Empty,Empty,Empty)),(4,Empty,Empty,Empty))"
"(1,(2,Empty,Empty,Empty),(3,(5,Empty,Empty,Empty),(6,Empty,Empty,Empty),(7,Empty,Empty,Empty)),(4,Empty,Empty,Empty))"

(b) オブジェクトとこのようなツリーを引数として、オブジェクトがツリーのノードのデータフィールドにeqlであるときに真を返す関数

-- MyNodeから値を検索する
findMyNode :: (Show a, Show d) => a -> (MyNode d l c r) -> Bool
findMyNode _ Empty = False
findMyNode a (MyNode d l c r) = if ((show a) == (show d)) then True
                                else (findMyNode a l) || (findMyNode a c) || (fi
ndMyNode a r)

main = do print $ showMyNode rootNode
          print $ showMyNode $ copyMyNode rootNode
          print $ findMyNode 5 rootNode
          print $ findMyNode 8 rootNode

大分ムリヤリですが、結果はこう。

True
False

MyNodeのdを型クラスEqに縛れれば良いのかと思うのですが、そういうことって出来ないんですかね。
MyNode自体をEqに縛ることは、もちろんできますが。