haskell_15day.md

haskell_15day.md

データ型

++

infixr 5 ++ -- infixr: 結合度
(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

++は標準で用意されている

:-:

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

^++

(^++) :: List a -> List a -> List a
Empty      ^++ ys = ys
(x :-: xs) ^++ ys = x :-: (xs ^++ ys)

使用例：

let a = 3 :-: 4 :-: 5 :-: Empty
let b = 6 :-: 7 :-: Empty

let c = a ^++ b
-- 3 :-: 4 :-: 5 :-: 6 :-: 7 :-: Empty

二分木

二分木をつくろう！

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

-- root作成
singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

-- 要素aをTreeに挿入
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree => singleton x
treeInsert x (Node a left right)
  | x == a = Node x left right
  | x <  a = Node a (treeInsert x left) right
  | x >  a = Node a left (treeInsert x right)


-- Treeに要素aが入っているかどうか
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
 | x == a = True
 | x <  a = treeElem x left
 | x >  a = treeElem x right
 
-- 二分木を作成
let nums = [8, 6, 4, 1, 7, 3, 5]
let numsTree = foldr treeInsert EmptyTree nums

• Q. なんでfoldr？
  • foldr: foldr (関数）（初期値）（配列）
    • 関数に初期値と配列の一要素が引数として実行される

foldr treeInsert EmptyTree [8, 6, 4, 1, 7, 3, 5]
-- (treeInsert 5 (treeInsert3 .... (treeInsert 8 EmptyTree)))))))

foldl treeInsert EmptyTree [8, 6, 4, 1, 7, 3, 5]
-- (treeInsert (treeInsert EmptyTree 8) 6) ..... 5)