Typage

Types d'expressions

Donnez les types des expressions suivantes :

1. ['a', 'b', 'c']

   Indice

   Solution

   [Char] || String

   Aller au plus simple. Qu'est-ce qu'une liste de caractères ?

2. ([False, True], ['0', '1'])

   Solution

   ([Bool], [Char])

3. [(False, '0'), (True, '1')]

   Solution

   [(Bool, Char)]

4. (['a', 'b'], 'c')

   Solution

   ([Char], Char)

5. [tail, init, reverse]

   Solution

   [([a] -> [a])]

6. take 5

   Solution

   [a] -> [a]

Types de fonctions

Donnez le type des fonctions suivantes :

1. second xs = head (tail xs)

   Solution

   second :: [a] -> a

2. swap (x, y) = (y, x)

   Solution

   swap :: (a, b) -> (b, a)

3. pair x y = (x, y)

   Solution

   pair :: a -> b -> (a, b)

4. fst (x, _) = x

   Solution

   fst :: (a, b) -> a

5. double x = x * 2

   Solution

   double :: Num a => a -> a

6. palindrome xs = reverse xs == xs

   Solution

   palindrome :: [a] -> Bool

7. twice f x = f (f x)

   Solution

   twice :: (a -> a) -> a -> a

8. j x = (x, [x], [x + 1])

   Solution

   j :: Num a => a -> (a, [a], [a])

9. n f x y = f (x + y)

   Solution

   Num a => (a -> b) -> a -> a -> b

Types plus complexes

Pour chacune des questions suivantes, écrivez le type le plus général correspondant à la fonction décrite.

1. data Tree a = Leaf a | Node (Tree a) a (Tree a)
   
   tS (Leaf x)     = x
   tS (Node l x r) = tS l + x + tS r

   Indice

   Solution

   tS :: Num a => Tree a -> a

   Attention au type de la structure.

2. data Tree a = Leaf a | Node (Tree a) a (Tree a)
   
   tS (Leaf x)     = x
   tS (Node l x r) = tS l <= x && x <= tS r

   Indice

   Solution

   tS :: Ord a => Tree a -> Bool

   Attention au type de la structure.

3. data Expr = Val Float | Add Expr Expr | Mul Expr Expr
   
   eval (Val n) = n
   eval (Add x y) = eval x + eval y
   eval (Mul x y) = eval x * eval y

   Solution

   eval :: Expr -> Float

4. data Graph a = Graph [(a, [a])]
   
   neighbors x (Graph edges) = concat [ns | (v, ns) <- edges, v == x]

   Solution

   neighbors :: Eq a => a -> Graph a -> [a]

5. data State = State String
   data Transition = Transition State State
   nextState _ [] = Nothing
   nextState orig@(State s) (Transition (State from) to : ts) 
     | s == from = Just to 
     | otherwise = nextState orig ts

   Solution

   nextState :: State -> [Transition] -> Maybe State