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

Size: px

Start display at page:

Download "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"

くにもとよせ
4 years ago
Views:

1 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] Bob String y Charlie Foo Double Integer Alice 3.14 [1,2], Bob "Hello" 3, Charlie,... C Java enum 1 data Direction = North South West East 2 deriving (Eq,Ord,Show) North, South, West, East 4 Direction deriving... Q (Rock) (Scissors) (Paper) RPS III - 1

2 1 data Tree a = Empty Branch (Tree a) a (Tree a) 2 deriving (Eq, Ord, Show) Branch Empty 2 Empty Branch Branch Branch :: a Integer String Tree Integer Integer Tree (type constructor) Tree 1 tree1 :: Tree a 2 tree1 = Empty 3 tree2 :: Tree Integer 4 tree2 = Branch Empty 1 Empty 5 tree3 :: Tree String 6 tree3 = Branch (Branch Empty "a" Empty) 7 "b" (Branch Empty "c" Empty) 8 tree4 :: Tree Integer 9 tree4 = Branch (Branch Empty 1 Empty) 10 2 (Branch Empty 3 (Branch Empty 4 Empty)) tree Tree 1 top :: Tree a -> a 2 top (Branch _ a _) = a 3 4 isempty :: Tree a -> Bool 5 isempty Empty = True 6 isempty _ = False 7 8 size :: Tree a -> Integer -- size tree4 4 9 size Empty = 0 10 size (Branch l a r) = size l size r III - 2

3 Q RPS judgerps :: -> Ordering Ordering RPS -> RPS data Ordering = LT EQ GT deriving (Eq, Ord, Bounded, Enum, Read, Show) LT GT Tree depth :: Tree a -> Integer -- preorder :: Tree a -> [a] -- inorder :: Tree a -> [a] -- postorder :: Tree a -> [a] -- reflect :: Tree a -> Tree a -- 1 depth tree4, 2 preorder tree4, 3 inorder tree4, 4 postorder tree4, 5 reflect tree4 1 3, 2 [2,1,3,4], 3 [1,2,3,4], 4 [1,4,3,2], 5 Branch (Branch (Branch Empty 4 Empty) 3 Empty) 2 (Branch Empty 1 Empty) n PL/0 ( books/algorighme0) C data C = F { f1, f2 :: Int, f3 :: Bool } deriving (Eq, Ord, Show) data C = F Int Int Bool deriving (Eq, Ord, Show) = 1 v1 = F { f1 = 5, f2 = 12, f3 = False } 2 3 foo :: C -> Int 4 foo (F { f1 = x, f2 = y }) = x*x + y*y III - 3

4 foo v1 169 v1 f1 v1 5 = v1 { f2 = 3 } F { f1 = 5, f2 = 3, f3 = False } 3.2 ad-hoc dynamic binding, overloading C + int double Haskell 1 : twice x = x + x; x + Haskell 3.3 inheritance encapsulation 3 1 parametric III - 4

5 Q Haskell ML (constructor) (algebraic data type) Java String 3.5 Haskell Haskell Eq Haskell C == Integer Double (\ x -> x+x) == (\ x -> 2*x) Haskell III - 5

6 1 member x [] = False 2 member x (y:ys) = x==y member x ys 3 4 subset xs ys = all (\ x -> member x ys) xs member subset member 5 [1, 4, 7] [Integer] member "Kagawa" ["Tokushima", "Ehime", "Kochi"] [String] member (\ x -> x+x) [\ x -> x+1, \ x -> 2*x] member subset a -> [a] -> Bool [a] -> [a] -> Bool member subset? Scheme Haskell Haskell member subset member :: subset :: Eq a => a Eq type constraint Eq == Haskell Java class Eq Haskell Prelude 1 class Eq a where 2 Java Haskell III - 6

7 2 (==), (/=) :: a -> a -> Bool --!= 3 a /= b = not (a == b) -- a Eq a -> a -> Bool 2 (==), (/=) Direction Eq Direction Eq instance 1 instance Eq Direction where 2 North == North = True 3 South == South = True 4 West == West = True 5 East == East = True 6 _ == _ = False (/=) Tree deriving 1 instance Eq a => Eq (Tree a) where 2 Empty == Empty = True 3 Branch l1 n1 r1 == Branch l2 n2 r2 4 = l1 == l2 && n1 == n2 && r1 == r2 5 _ == _ = False Eq a => Tree a a Tree Eq 2 Eq Q Bool : data MyBool = MyTrue MyFalse Eq Bool Eq III - 7

8 Q Q RPS Eq Q size :: a -> Int Sizable 3.7 Eq Ord, Show, Num 1 class Eq a => Ord a where -- Ord order 2 (<), (<=), (>=), (>) :: a -> a -> Bool 3 max, min :: a -> a -> a class Show a where 7 show :: a -> String class (Eq a, Show a) => Num a where 11 (+), (-), (*) :: a -> a -> a 12 frominteger :: Integer -> a class Num a => Fractional a where 16 (/) :: a -> a -> a Ord Show Num Fractional => Eq Ord Ord Eq III - 8

9 Haskell 1 :: (Num t) => t 3.14 :: (Fractional t) => t 1 Int Double Show, Eq, Ord deriving [diráivin] Haskell 1 data Tree a = Empty Branch (Tree a) a (Tree a) 2 deriving (Eq, Ord, Show) Tree ==, >, show Q data MyList a = MyNil MyCons a (MyList a) deriving Eq Ord Ord Eq == Ord <= : MyList tomylist :: [a] -> MyList a tomylist [] = MyNil tomylist (x:xs) = MyCons x (tomylist xs) tomylist "abc" <= tomylist "abd" -- True tomylist "ab" <= tomylist "abc" -- True tomylist "ab" <= tomylist "a" -- False tomylist "ab" <= tomylist "ba" -- True III - 9

10 3.8 Haskell Haskell Haskell Integer Char [Integer] Show -- let impossible = [1, a,[1,4,7]] -- in map show impossible 3.9 (ambiguity) 1 class Show a where 2 show :: a -> String 3 class Read a where 4 read :: String -> a foo x = show (read x) foo :: (Show a, Read a) => String -> String a => foo x = show (read x :: Integer) a (monomorphism restriction) => III - 10

11 1 genericlength :: Num a => [b] -> a 2 genericlength [] = 0 3 genericlength (_:xs) = 1 + genericlength xs genericlength length :: 1 let v = genericlength [1,2,3,4] 2 in (v,v) [b] -> Int Dictionary-Passing Style 1 \ d1 d2 -> let v d = genericlength d [1,2,3,4] 2 in (v d1, v d2) genericlength DPS 2 2 DPS 1 \ d -> let v = genericlength d [1,2,3,4] 2 in (v, v) 2 v [4] f0 xs = map (+1) xs -- (+1) \ x -> x+1 -- f0 xs = map +1 xs 1 f0 :: (Num (t -> (a -> b) -> [a] -> [b]), 2 Num ((a -> b) -> [a] -> [b])) => 3 t -> (a -> b) -> [a] -> [b] 1 -- (-1) 2 -- f1 xs = map (\ x -> x-1) xs 3 f1 xs = map (-1) xs : III - 11

12 6 -- f2 n = n : [4,5,6] 7 f2 n = [n] : [4,5,6] Haskell f. g = \ x -> f (g x) f3 r = r * sin f3 r = r * sin.2 Q f1, f2, f Dictionary-Passing Style Haskell Haskell 1 type Eq a = 2 3 eq :: Eq a -> (a -> a -> Bool) 4 eq = \ (e, _) -> e -- (==) 5 6 ne :: Eq a -> (a -> a -> Bool) 7 ne = \ (_, n) -> n -- (/=) Eq a method dictionary 1 eqdirectiondic :: Eq Direction 2 eqdirectiondic = (eqdirection, \ a b -> not (a eqdirection b)) 3 where North eqdirection North = True 4 South eqdirection South = True 5 West eqdirection West = True 6 East eqdirection East = True 7 _ eqdirection _ = False III - 12

13 8 9 eqtreedic :: Eq a -> Eq (Tree a) 10 eqtreedic (eqa, _) = (eqtree, \ a b -> not (eqtree a b)) 11 where Empty eqtree Empty = True 12 Branch l1 n1 r1 eqtree Branch l2 n2 r2 13 = l1 eqtree l2 && n1 eqa n2 && r1 eqtree r2 14 _ eqtree _ = False... =>... Eq a 1 member :: -> a -> [a] -> Bool 2 member d x [] = False 3 member d x (y:ys) = eq d x y member d x ys 4 5 subset :: -> [a] -> [a] -> Bool 6 subset d xs ys = all (\ x -> member d x ys) xs member North [North, South, West] member North [North, South, West] subset [North, South] [North, South, West] subset [North, South] [North, South, West] Dictionary-Passing Style Haskell lookup: 1 data Maybe a = Just a Nothing 2 3 lookup :: Eq a => a -> [(a, b)] -> Maybe b 4 lookup x ((n,v):rest) = if n==x then Just v else lookup x rest 5 lookup x [] = Nothing lookup Dictionary-Passing Style lookupd: lookupd :: Eq a -> a -> [(a, b)] -> Maybe b lookup 1 [(1,2),(4,7)] lookupd eqintdic 1 [(1,2),(4,7)] lookup 1.1 [(1.4,0.1),(4.2,6.9)] 3 III - 13

14 lookupd eqdoubledic 1.1 [(1.4,0.1),(4.2,6.9)] eqintdic, eqdoubledic 3.11 Smalltalk [5] 6 JavaScript prototype Self JavaScript [6] 6 JavaScript Common Lisp CLOS multi-method 2 Java char, int double Scala C# Smalltalk[5], CLOS, JavaScript[6], C++, Java[7], Python, Ruby 3.12 Haskell III - 14

15 [1] [2] Haskell [3] Haskell Haskell [4] [1] Philip Wadler and Stephen Blott How to make ad-hoc polymorphism less adhoc Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, pp [2] Cordelia Hall, Kevin Hammond, Simon Peyton Jones and Philip Wadler Type Classes in Haskell 1996 ACM Transactions on Programming Languages and Systems 18 2, pp [3] Mark P. Jones Typing Haskell in Haskell mpj/thih/ [4] Bastiaan Heeren and Jurriaan Hage Type Class Directives Seventh International Symposium on Practical Aspects of Declarative Languages (LNCS 3350), pp [5] Mark Guzdial and Kim Rose Squeak [6] JavaScript ASCII [7] Tim Lindholm and Frank Yellin Java III - 15

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

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 3 Haskell Haskell Haskell 1. 2. 3. 4. 5. 1. 2. 3. 4. 5. 6. C Java 3.1 Haskell Haskell GHC (Glasgow Haskell Compiler 1 ) GHC Haskell GHC http://www.haskell. 1 Guarded Horn Clauses III - 1 org/ghc/ Windows