2 - PDF 無料ダウンロード

2011.11.11 1

MapReduce 3

Functional Functional Programming 7

[10, 20, 30, 40, 50] 0 n n 10 * 0 + 20 * 1 + 30 * 2 + 40 * 3 + 50 *4 = 400 14

10 * 0 + 20 * 1 + 30 * 2 + 40 * 3 + 50 *4 = 400 for 15

for Douglas Crockford JavaScript: http://www.crockford.com/javascript/javascript.html for JavaScript C JavaScript C Java Lisp Scheme 16

for 17

for for for for for ) for two days for (i = 0; i < N; i++) { } 0 N = - + 1 (N - 1) - 0 + 1 = N 1/3 + 1/3 + 1/3 1 18

JavaScript for function func(ar) { var ret = 0; for (var i=0; i < ar.length; i++) { ret = ret + ar[i]*i; } return ret; } func([10,20,30,40,50]); 400 19

Haskell MapReduce zip [0..] [10,20,30,40,50] [(0,10),(1,20),(2,30),(3,40),(4,50)] map (\(i,x) -> x*i) [0,20,60,120,200] foldl (+) 0 ((((0 + 0) + 20) + 60) + 120) + 200 400 func = foldl (+) 0. map (\(i,x) -> x*i). zip [0..] func [10,20,30,40,50] 400 20

head (car, first) tail (cdr, rest) : (cons) 24

-- [1,2,3] -- 1 : 2 : 3 : [] : (cons) -- 1 : (2 : (3 : [])) : a : [ b, o, a, r, d ] [ a, b, o, a, r, d ] head tail sum [] = 0 sum (x:xs) = x + sum xs 26

(1) ++ (append) zs = xs ++ ys ++ 1) 27

(2) ++ O(N) xs ++ (ys ++ zs) ++ O(N^2) (xs ++ ys) ++ zs ++ 2) 28

factorial(0) = 1 factorial(n) = n * factorial(n - 1) factorial :: Int -> Int -- factorial 0 = 1 -- factorial n = n * factorial (n-1) 31

length :: [Int] -> Int length [] = 0 length (x:xs) = 1 + length xs 33

( ) 34

( ) Haskell = (++) :: [a] -> [a] -> [a] [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) {- (++) (x:xs) ys = (:) x (xs ++ ys) -} delay force 35

( ) sum :: Num a => [a] -> a sum [] = 0 sum (x:xs) = x + sum xs {- sum (x:xs) = (+) x (sum xs) -} sum [1,2,3,4] = 1 + sum [2,3,4] = 1 + (2 + sum [3,4]) = 1 + (2 + (3 + sum [4])) = 1 + (2 + (3 + (4 + sum []))) = 1 + (2 + (3 + (4 + 0))) 36

sum :: Num a => [a] -> a sum xs = sum 0 xs where sum r [] = r sum r (y:ys) = sum (y+r) ys sum 0 [1,2,3,4] = sum 1 [2,3,4] = sum 3 [3,4] = sum 6 [4] = sum 10 [] = 10 37

MapReduce 39

[1,2,3,4] 1 + (2 + (3 + (4 + 0))) [1,2,3,4] (((0 + 1) + 2) + 3) + 4 40

foldr foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ ini [] = ini foldr op ini (x:xs) = op x (foldr op ini xs) ( ) ++ foldr (++) :: [a] -> [a] -> [a] xs ++ ys = foldr (:) ys xs 41

foldl foldl :: (a -> b -> a) -> a -> [b] -> a foldl _ acc [] = acc foldl op acc (x:xs) = foldl op (op acc x) xs sum foldl sum :: Num a => [a] -> a sum xs = foldl (+) 0 xs 42

map map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs foldr map :: (a -> b) -> [a] -> [b] map f xs = foldr (\y ys -> f y:ys) [] xs 43

filter filter :: (a -> Bool) -> [a] -> [a] filter _ [] = [] filter prd (x:xs) prd x = x : filter prd xs otherwise = filter pred xs foldr filter :: (a -> Bool) -> [a] -> [a] filter prd xs = foldr filter [] xs where filter y ys prd y = y : ys otherwise = ys 44

sumeven :: [Int] -> Int sumeven xs = sumeven xs 0 where sumeven [] r = r sumeven (y:ys) r even y = sumeven ys (y + r) otherwise = sumeven ys r MapReduce sumeven :: [Int] -> Int sumeven xs = foldl (+) 0 (filter even xs) {- sumeven = foldl (+) 0. filter even -} 46

"String" = [ S, t, r, i, n, g ] 49

"Subject: Hello world " key = "Subject" val = "Hello world" 50

JavaScript var target = "Subject: Hello world "; var x = target.match(/^(\w+):\s*(.*)/); var key = x[1]; var val = x[2].replace(/\s*$/,""); 51

target = "Subject: Hello world " break (== : ) target ("Subject", ": Hello world ") tail (snd ) " Hello world " dropwhile isspace "Hello world " dropwhileend isspace "Hello world" 52

break :: (a -> Bool) -> [a] -> ([a],[a]) break _ [] = ([],[]) break p (x:xs) p x = ([],x:xs) otherwise = (x:ys,zs) where (ys,zs) = break p xs dropwhile :: (a -> Bool) -> [a] -> [a] dropwhile _ [] = [] dropwhile p (x:xs) p x = dropwhile p xs otherwise = x:xs dropwhileend :: (a -> Bool) -> [a] -> [a] dropwhileend p = foldr op [] where op x xs p x && null xs = [] otherwise = x:xs 53

Ask not what your country can do for you, but what you can do for your country. "can do for you" 54

( ) tails tails "banana" ["banana","anana","nana","ana","na","a",""] tails tails :: [a] -> [[a]] tails [] = [[]] tails xs = xs : tails (tail xs) 55

(1) tails "mississippi" ["mississippi","ississippi", "ssissippi","sissippi",... sort ["","i","ippi","issippi", "ississippi","mississippi","pi",... zip (tail ) [("","i"),("i","ippi"), ("ippi","issippi"), ("issippi","ississippi"),... 56

(2) comlen :: Eq a => [a] -> [a] -> Int comlen as bs = comlen as bs 0 where comlen (x:xs) (y:ys) n x == y = comlen xs ys (n+1) comlen n = n lenstr :: Eq a => ([a], [a]) -> (Int,[a]) lenstr (xs,ys) = (len,xs) where len = comlen xs ys 57

(3) [("","i"),("i","ippi"), ("ippi","issippi"), ("issippi","ississippi"),... map lenstr [(0,""),(1,"i"),(1,"ippi"), (4,"issippi"),(0,"ississippi"),... maximumby (comparing fst) (4,"issippi") take (fst ) (snd ) "issi" 58

data List a = Nil Cons a (List a) data Tree a = Tip Bin a (Tree a) (Tree a) 61

10,000 13 62

(1) preorder :: Tree a -> [a] preorder Tip = [] preorder (Bin x l r) = [x] ++ preorder l ++ preorder r inorder :: Tree a -> [a] inorder Tip = [] inorder (Bin x l r) = inorder l ++ [x] ++ inorder r postorder :: Tree a -> [a] postorder Tip = [] postorder (Bin x l r) = postorder l ++ postorder r ++ [x] 63

(2) preorder :: Tree a -> [a] preorder t = go t [] where go Tip xs = xs go (Bin x l r) xs = x : (go l (go r xs)) inorder :: Tree a -> [a] inorder t = go t [] where go Tip xs = xs go (Bin x l r) xs = go l (x : (go r xs)) postorder :: Tree a -> [a] postorder t = go t [] where go Tip xs = xs go (Bin x l r) xs = go l (go r (x : xs)) 64

O(1) Finite Map ( ) 67

= DSL data Parser a = Parser (String -> (Maybe a, String)) char :: Char -> Parser Char char c =... (< >) :: Parser a -> Parser a -> Parser a p1 < > p2 =... 70

JSON BNF (RFC 4627) value = object / array / number / string... JSON value :: Parser JSON value = jsobject < > jsarray < > jsnumber < > jsstring... BNF ( ) 71

7 7 Scala Erlang Clojure Haskell Scheme Haskell Scala OCaml Purely Functional Data Structure Haskell ( ) 74