org/ghc/ Windows Linux RPM 3.2 GHCi GHC gcc javac ghc GHCi(ghci) GHCi Prelude> GHCi :load file :l file :also file :a file :reload :r :type expr :t exp

Size: px

Start display at page:

Download "org/ghc/ Windows Linux RPM 3.2 GHCi GHC gcc javac ghc GHCi(ghci) GHCi Prelude> GHCi :load file :l file :also file :a file :reload :r :type expr :t exp"

ひとおこけい
6 years ago
Views:

1 3 Haskell Haskell Haskell C Java 3.1 Haskell Haskell GHC (Glasgow Haskell Compiler 1 ) GHC Haskell GHC 1 Guarded Horn Clauses III - 1

2 org/ghc/ Windows Linux RPM 3.2 GHCi GHC gcc javac ghc GHCi(ghci) GHCi Prelude> GHCi :load file :l file :also file :a file :reload :r :type expr :t expr :cd directory :c :! command command :? :quit :q GHCi Prelude> Haskell 3.3 Haskell Haskell Haskell Haskell C = III - 2

3 { } 1 = 1 ; 2 = 2 ;... ; n = n { } ; C _ Haskell 1 module where module where { 1 = 1 ; 2 = 2 ;... ; n = n } import 1 1 module where Main Haskell 1 = 1 2 = 2... n = n Haskell λ Y=. λx.x λxy.y Haskell III - 3

4 C c0 = \ f x -> x c1 = \ f x -> f x c2 = \ f x -> f (f x) true = \ t f -> t false = \ t f -> f = c0 f x = x c1 f x = f x c2 f x = f (f x) true t f = t false t f = f Haskell Haskell Bool Int, Integer Int, Integer Float, Double Char Bool Integer, Float, Double, Char C Lisp +, -, * 1+2*3 if then else if 1 then 2 else True 2 False 3 if then else Haskell factorial Haskell fact n = if n==0 then 1 else n*fact(n-1) fact(n-1) fact n-1 n*(fact(n-1)) fact 100 III - 4

5 Scheme Lisp Haskell (cons) [] : : 1:2:[] 1:(2:[]), [ ] [1,2,3,4] Integer Double Haskell String type String = [Char] type = type alias String [Char] box-pointer xs0 = [] xs1 = 1:xs0 xs2 = 2:xs1 xs3 = 3:xs2 xs3 xs2 xs : 2 1, 2, 3 [[1,2],[3,4]] III - 5

6 box-pointer 1. [2,3,5,7,11] 2. [0] 3. [[1],[2,3,4],[]] C struct _list { int car; struct _list* cdr; }; typedef struct _list* list; _list car cdr 2 cdr list typedef struct _list* C C NULL malloc C free Haskell free tuple, ( ) (1, a ) (2, b, [3]) 2 -> Integer -> Char Integer Char -> Bool -> Bool -> Bool 2 Haskell type class III - 6

7 Integer Char a b [a] -> [b] -> [(a, b)] [Char] -> [Integer] -> [(Char, Integer)] [String] -> [Integer -> Integer] -> [(String, Integer -> Integer)] Haskell :: :: fact fact :: Integer -> Integer fact n = if n==0 then 1 else n*fact(n-1) Haskell 3.5 Haskell 3 -- Prelude length mylength :: [a] -> Integer mylength [] = 0 mylength (x:xs) = 1 + mylength xs mylength [] x xs mylength length :: [a] -> Int _ mylength x mylength (_:xs) = 1 + mylength xs case of case of case 0 of { 1 -> 1 ; 2 -> 2 ; 3 III - 7

8 }... n -> n m m if 1 then 2 else 3 case of case 1 of { True -> 2 ; False -> 3 } let λ \ (x:xs) -> x head mysum [Bool] 2 frombin :: [Bool] -> Integer frombin [True, True] 3, frombin [True, False, True, False] 10 : xs f f sumf :: [Double] -> (Double -> Double) -> Double reverse: -- append Prelude (++) append :: [a] -> [a] -> [a] append [] ys = ys append (x:xs) ys = x : (append xs ys) -- reverse Prelude reverse :: [a] -> [a] reverse [] = [] reverse (x:xs) = append (reverse xs) [x] III - 8

9 -- shunt rev shunt :: [a] -> [a] -> [a] shunt ys [] = ys shunt ys (x:xs) = shunt (x:ys) xs rev :: [a] -> [a] rev xs = shunt [] xs rev rev reverse xs rev xs = reverse xs shunt ys xs = append (reverse xs) ys : xs = [] : xs = z:zs : xs append xs (append ys zs) = append (append xs ys) zs xs III - 9

10 3.7 Prelude map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs zipwith :: (a -> b -> c) -> [a] -> [b] -> [c] zipwith f (x:xs) (y:ys) = f x y : zipwith xs ys zipwith f = [] filter :: (a -> Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) = if p x then x : filter p xs else filter p xs iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x) foldr :: (a -> b -> b) -> b -> [a] -> b foldr f x [] = x foldr f x (y:ys) = f y (foldr f x ys) foldl :: (a -> b -> a) -> a -> [b] -> a foldl f x [] = x foldl f x (y:ys) = foldl (f x y) ys 3.8 Haskell Prelude zip zip :: [a] -> [b] -> [(a,b)] zip (a:as) (b:bs) = (a,b) : zip as bs zip = [] zip [1, 2] [3, 4] [1, 2] zip [3, 4] infixl, infixr, infix III - 10

11 Prelude Haskell infixr 9. infixl 9!! infixr 8 ˆ, ˆˆ, ** infixl 7 *, /, quot, rem, div, mod, :%, % infixl 6 +, - infixr 5 : infixr 5 ++ infix 4 ==, /=, <, <=, >=, >, elem, notelem infixr 3 && infixr 2 infixl 1 >>, >>= infixr 1 =<< infixr 0 $, $!, seq infixl infixr infix 1 < x < 2 2 * + ( ) 1+2 (+) 1 2 let let in pow4 x = let y = x*x in y*y -- head Prelude head ys = let (x:xs) = ys in x 4 pow4 y*y y -- repeat Prelude repeat :: a -> [a] repeat x = let xs = x:xs in xs x Prelude> repeat 1 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,... 4 Haskell Haskell evalpoly :: [Double] -> Double -> Double [1, 2, 3, 4] 1 + 2x + 3x 2 + 4x 3 evalpoly [1, 2, 3, 4] Ctrl-c III - 11

12 3.8.2 powerset powerset [1, 2, 3] [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]] 3.9 algebraic datatype data k = 1 1,1... 1,n1 2 2,1... 2,n2... m m,1... m,nm C enum data Direction = Up Down Left Right Up, Down, Left, Right 4 Direction data Tree a = Branch (Tree a) a (Tree a) Empty Branch Empty 2 Empty Branch Branch Branch :: a Integer String Tree Integer Integer Tree (type constructor) Tree Empty :: Tree a Branch Empty 1 Empty :: Tree Integer Branch (Branch Empty "a" Empty) "b" (Branch Empty "c" Empty) :: Tree String Branch (Branch Empty 1 Empty) 2 (Branch Empty 3 (Branch Empty 4 Empty)) :: Tree Integer III - 12

13 Tree size :: Tree a -> Integer -- depth :: Tree a -> Integer -- preorder :: Tree a -> [a] -- postorder :: Tree a -> [a] -- reflect :: Tree a -> Tree a Haskell Haskell twice twice x = x*x twice (2+2) twice (2 + 2) = (2 + 2) (2 + 2) = 4 4 = 16 twice (2+2) twice ( * ) twice * * 4 16 lazy evaluation III - 13

14 from :: Integer -> [Integer] from n = n : from (n+1) -- take Prelude take :: Integer -> [a] -> [a] take 0 _ = [] take _ [] = [] take n (x:xs) = x : take (n-1) xs from 1 [1, 2, 3,... ] take 3 (from 1) take 3 (from 1) take 3 (1:from (1+1)) 1:(take 2 (from (1+1))) 1:(take 2 ((1+1):from (1+1+1))) 1:(1+1):(take 1 (from (1+1+1))) 1:(1+1):(1+1+1):(take 0 (from ( ))) 1:(1+1):(1+1+1):[] (=[1, 2, 3]) from.. Prelude> [1..] [1,2,3,4,5,6,7,8,9,10,11,... Prelude> [2,4..] [2,4,6,8,10,12,14,16,18,20,22,... Prelude> [1..10] [1,2,3,4,5,6,7,8,9,10] Prelude> [1,4..20] [1,4,7,10,13,16,19] [6] take n mydrop :: -> [a] Integer -> [a] fib merge i 3 j 5 k i, j, k 0 hamming Haskell 3.11 List Comprehension Haskell List Comprehension syntax sugar III - 14

15 Prelude> [(x, y) x <- [1, 2, 3, 4], y <- [5, 6, 7]] [(1,5),(1,6),(1,7),(2,5),(2,6),(2,7),(3,5),(3,6),(3,7),(4,5),(4,6),(4,7)] Prelude> [x*x x <- [1..10], odd x] [1,9,25,49,81] [1..10] [1,2,3,4,5,6,7,8,9,10] [,..., ] Bool : < n 0 x y n x, y foo :: Integer -> [(Integer, Integer)] n 0 < x < y < z n x 2 + y 2 = z 2 x, y, z chokkaku :: Integer -> [(Integer, Integer, Integer)] -- 1 unit :: a -> [a] unit a = a : [] bind :: [a] -> (a -> [b]) -> [b] bind [] _ = [] bind (x:xs) f = append (f x) (bind xs f) [t] unit t [t x <- u, P] bind u (\ x -> [t P]) [t b, P] if b then [t P] else [] b Bool P qsort [] = [] qsort (x:xs) = qsort [ y y <- xs, y < x] ++ x : qsort [ y y <- xs, y >= x] unit, bind 1. [(x, y) x <- [1, 2, 3, 4], y <- [5, 6, 7]] 2. [x*x x <- [1..10], odd x] primes [2, 3, 5, 7, 11,... ] III - 15

16 : (Eratosthenes) C [4, 6, 1, 5, 2, 8, 3, 7] III - 16

17 safe p n length p p length p + 1 n safe p n = all not [ check (i, j) (1+length p, n) (i, j) <- zip [1..] p ] check (i,j) (m,n) = j==n (i+j==m+n) (i-j==m-n) all all all p [] all p (x:xs) :: (a -> Bool) -> [a] -> Bool = True = if p x then all p xs else False [1..] [1, 2, 3,... ] > safe [1, 3] 5 True > safe [1, 3] 2 False m ( ) queens III - 17

18 queens 0 = [[]] queens m = [ append p [n] p<-queens (m-1), n<-[1..8], safe p n ] > queens 1 [[1], [2], [3], [4], [5], [6], [7], [8]] > queens 2 [[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,4],[2,5],[2,6],[2,7],[2,8], [3,1],[3,5],[3,6],[3,7],[3,8],[4,1],[4,2],[4,6],[4,7],[4,8],[5,1], [5,2],[5,3],[5,7],[5,8],[6,1],[6,2],[6,3],[6,4],[6,8],[7,1],[7,2], [7,3],[7,4],[7,5],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6]] head (queens 8) > head (queens 8) [1,5,8,6,3,7,2,4] [1, 5, 8, 6, 3, 7, 2, 4] queens 7 queens 7 head (queens 8) Prolog (backtrack) 1 1 queens 8 > queens 8 [[1,5,8,6,3,7,2,4],[1,6,8,3,7,4,2,5], ( ),[8,3,1,6,2,5,7,4],[8,4,1,3,6,2,7,5]] 92 [1] Haskell A Purely Functional Language featuring static typing, higher-order functions, polymorphism, type classes and monadic effects Haskell [2] Programming in Haskell Haskell [3] Simon Peyton Jones, John Hughes Haskell 98: A Non-strict, Purely Functional Language , Haskell Haskell [4] Mark P Jones, Alastair Reid The Hugs 98 User Manual Haskell Hugs III - 18

19 [5] Simon Peyton Jones, David Lester Implementing Functional Languages Prentice Hall, Haskell [6] John Hughes Why Functional Programming Matters 1989, rjmh/papers/whyfp.html [7] Philip Wadler List Comprehensions Simon Peyton Jones The Implementation of Functional Programming Languages Prentice Hall, [8] Haskell [9] Simon Peyton Jones Wearing the hair shirt A retrospective on Haskell 2003, simonpj/papers/haskell%2dretrospective/ Haskell Haskell [10] Richard Bird, Philip Wadler, , ISBN Haskell Miranda [11] Haskell, , ISBN [12] Haskell, , ISBN III - 19

3 3.1 algebraic datatype data k = 1 1,1... 1,n1 2 2,1... 2,n2... m m,1... m,nm 1 m m m,1,..., m,nm m 1, 2,..., k 1 data Foo x y = Alice x [y] B

3 3.1 algebraic datatype data 1 2... k = 1 1,1... 1,n1 2 2,1... 2,n2... m m,1... m,nm 1 m m m,1,..., m,nm m 1, 2,..., k 1 data Foo x y = Alice x [y] Bob String y Charlie Foo Double Integer Alice 3.14 [1,2],