Quiz Haskell: une simple fonction

Question

Je ne suis pas un programmeur Haskell, mais je suis curieux de connaître les questions suivantes.

spécification de la fonction informelle:

Soit mondePlan une fonction qui prend une fonction appelée F et plusieurs listes. Il renvoie une liste contenant les résultats de l'appel de F avec un argument de chaque liste dans chaque combinaison possible.

Exemple:

Appel mondePlan avec F étant une fonction qui renvoie simplement une liste de ses arguments, et deux listes. Une des listes contient les entiers 1 et 2, l'autre contient les chaînes "a" et "b". Il devrait retourner une liste qui contient les listes: 1 et "a", 1 et "b", 2 et "a", 2 et "b".

Questions:

• Comment est mondePlan mis en œuvre?
• Quel est le type de la fonction? Quel est le type de F?
• Peut-on deviner ce que la fonction fait juste en regardant son type?
• Pouvez-vous gérer des listes inhomogènes en entrée? (par exemple 1 et "a" dans l'une des listes d'entrée)
• Quelle limitation supplémentaire (le cas échéant) devez-vous introduire pour implémenter MapProduct?

Answer 1

• Comment est mis en œuvre mondePlan?

.

Prelude> :m + Control.Applicative 
Prelude Control.Applicative> (,,) <$> [1,2,3] <*> ["a","b","c"] <*> [0.8, 1.2, 4.4] 
[(1,"a",0.8),(1,"a",1.2),...,(3,"c",4.4)] 

• Quel est le type de la fonction? Quel est le type de F?

Le type de F dépend de la liste que vous souhaitez appliquer. <$> ici est fmap, et (<*>) :: f(a->b) -> f a -> f b où f = [] ici.

• Pouvez-vous gérer les listes inhomogène en entrée? (Par exemple 1 et « a » dans l'une des listes d'entrée)

Il n'y a pas une telle chose comme hétérogène liste. Mais vous pouvez simulate a heterogeneous list for a specific context with existential types. Et puis vous pouvez simplement utiliser la méthode ci-dessus pour faire le MapProduct.

*Main Control.Applicative> :i SB 
data ShowBox where 
    SB :: forall s. (Show s) => s -> ShowBox 
    -- Defined at v.hs:1:35-36 
*Main Control.Applicative> [SB 2, SB "a", SB 6.4] 
[2,"a",6.4] 
*Main Control.Applicative> (,) <$> [SB 2, SB "a", SB 6.4] <*> [SB 'z', SB 44] 
[(2,'z'),(2,44),("a",'z'),("a",44),(6.4,'z'),(6.4,44)] 

Answer 2

La fonction que vous décrivez est étroitement liée aux fonctions zipWithN. Il aura le même type - cela donnera seulement des listes de résultats plus grandes. Maintenant le problème est qu'il n'y a aucun moyen d'exprimer "une fonction qui prend N arguments du type t_1, ..., t_n" ou "n listes des types [t_1],...,[t_n]" (ou "un n-uplet de type ([t_1], ..., [t_n]")) dans le système de type de haskell (sans extensions . comme modèle de haskell) Ceci est la raison pour laquelle il n'y a pas une fonction zipWith, mais pour chaque nombre d'arguments listes qui est supporté

donc, pour répondre à vos questions.

• Il est mis en œuvre en définissant un function mapProductN pour chaque numéro N que vous voulez prendre en charge.Pour N = 2 cela ressemblerait à ceci:

  mapProduct f l1 l2 = [f x1 x2 | x1 <- l1, x2 <- x2] 
  

  Ou en tant que plan général (c.-à-d. pseudo-code) comment définir les fonctions de toute N:

  mapProduct f l1 ... ln = [f x1 ... xn | x1 <- l1, ..., xn <- ln] 
  

• Comme je l'ai dit qu'il était le même que les types des fonctions zipWith, à savoir:

  zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] 
  zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] 
  zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e] 
  

  Comme f est le premier argument à la fonction, le type du premier argument est le type de f (donc pour n = 2 ce serait a -> b -> c)

• Eh bien, car il a le même type que zipWith et zipWith fait quelque chose d'autre, ce serait un non.

• Haskell n'autorise pas les listes inhomogènes sans extension.

• Il existe une limite supérieure pour le nombre de listes, sauf si vous êtes prêt à passer du temps à écrire des versions infinies de mapProduct.

Answer 3

Il est possible de définir une fonction mapProduct qui fonctionne pour toute arité de la fonction:

{-# LANGUAGE FlexibleInstances, TypeFamilies #-} 

module MapProduct (
    mapProduct 
    ) where 

import Control.Monad 

newtype ProdFuncList a b = ProdFuncList [ a -> b ] 


class MapProdResult p where 
    type MapProdArg p 
    apNext :: ProdFuncList x (MapProdArg p) -> [x] -> p 

instance (MapProdResult b) => MapProdResult ([a] -> b) where 
    type MapProdArg ([a] -> b) = (a -> MapProdArg b) 
    apNext (ProdFuncList fs) = apNext . ProdFuncList . ap fs 

instance MapProdResult [b] where 
    type MapProdArg [b] = b 
    apNext (ProdFuncList fs) = ap fs 


mapProduct :: (MapProdResult q) => (a -> MapProdArg q) -> [a] -> q 
mapProduct f = apNext (ProdFuncList [f]) 

Ici, il est en action:

> :l MapProduct.hs 
[1 of 1] Compiling MapProduct  (MapProduct.hs, interpreted) 
Ok, modules loaded: MapProduct. 
> mapProduct (+10) [1..4] :: [Int] 
[11,12,13,14] 
> mapProduct (*) [1..4] [10..12] :: [Int] 
[10,11,12,20,22,24,30,33,36,40,44,48] 
> mapProduct (\a b c -> a:b:c:[]) "bcs" "ao" "dnt" :: [String] 
["bad","ban","bat","bod","bon","bot","cad","can","cat","cod","con","cot","sad","san","sat","sod","son","sot"] 

L'inconvénient de cette approche est que vous devrez probablement taper annoter le résultat (comme indiqué dans les exemples ci-dessus). Il serait beaucoup plus idiomatiques à utiliser simplement fmap et ap directement:

> :m + Control.Monad 
> (+10) `fmap` [1..4] 
[11,12,13,14] 
> (*) `fmap` [1..4] `ap` [10..12] 
[10,11,12,20,22,24,30,33,36,40,44,48] 
> (\a b c -> a:b:c:[]) `fmap` "bcs" `ap` "ao" `ap` "dnt" 
["bad","ban","bat","bod","bon","bot","cad","can","cat","cod","con","cot","sad","san","sat","sod","son","sot"] 

Ce pas d'annotations de type nécessite, et est entièrement générale sur toutes les monades, pas seulement [].

(Le module mondePlan ci-dessus pourrait facilement être généralisée sur toutes les monades aussi bien. Je ne pas à le rendre clairement résoudre la question initiale.)