Haskell: Fonction pour appliquer une fonction aux 2-tuples imbriqués

Question

Dites que j'ai un tuple comme ('a',(1,("Hello",False)). Juste pour le plaisir (lire: apprentissage), je voudrais créer une fonction qui applique une fonction de la forme correcte à un tel tuple et renvoie le résultat. Exemple d'utilisation:

applyFnToTuple ('o',('t','w')) $ \a b c -> [a,b,c] == "otw" 
applyFnToTuple ('h','i') $ \a b -> [a,b] == "hi" 
applyFnToTuple ("hello",('y','o')) $ \a b c -> a ++ [b,c] 

je l'ai fait la plus grande partie comme suit:

type family TupleFn ty out where 
    TupleFn (a,b) output = a -> (TupleFn b output) 
    TupleFn b output = b -> output 

class ApplyFnToTuple a where 
    applyFnToTuple :: a -> TupleFn a out -> out 

instance ApplyFnToTuple b => ApplyFnToTuple (a,b) where 
    applyFnToTuple (a,b) fn = applyFnToTuple b (fn a) 

instance ApplyFnToTuple a where 
    applyFnToTuple b fn = fn b 

Le point d'achoppement est que dernière instance. Je m'attends entièrement à devoir ajouter {-# OVERLAPPABLE #-} puisque a est plus général que le (a,b). Je ai aussi du mal à voir exactement comment GHC pourrait résoudre a et la version correcte de ma classe TupleFn et connaître le bon type sig, mais je peux facilement mettre cela à mon propre manque de compréhension. Mais en tout cas, l'erreur réelle GHCi me donne est:

Couldn't match expected type ‘a -> out’ 
       with actual type ‘TupleFn a out’ 
    Relevant bindings include 
     fn :: TupleFn a out (bound at examples.hs:574:22) 
     b :: a (bound at examples.hs:574:20) 
     applyFnToTuple :: a -> TupleFn a out -> out 
     (bound at examples.hs:574:5) 
    The function ‘fn’ is applied to one argument, 
    but its type ‘TupleFn a out’ has none 
    In the expression: fn b 
    In an equation for ‘applyFnToTuple’: applyFnToTuple b fn = fn b 
Failed, modules loaded: none. 

Pour autant que je sache, aucune version de mon TupleFn retourne quelque chose sans argument, donc je ne comprends pas vraiment l'erreur. Cependant, je trouve qu'il peut être fait de compiler simplement en changeant la dernière instance à quelque chose par exemple plus concret:

instance ApplyFnToTuple Char where 
    applyFnToTuple b fn = fn b 

Mais cela signifie que je dois définir beaucoup de cas similaires, etc ce qui est indésirable.

Ce que je voudrais savoir, est-ce qu'il ya un moyen relativement facile de faire fonctionner la version plus générale, et pourquoi cette erreur particulière?

:) Merci

PS: Je suis en GHC 7.10.1

Answer 1

Le problème est que dans les la définition du instance ApplyFnToTuple a, il n'y a pas d'accès à l'information que a n'est pas un tuple - Je suppose que GHC ne considère pas comment l'instance pourrait être choisie pour décider si elle est correcte en tant que définition. Cela signifie qu'il ne peut pas savoir que TupleFn donne le bon résultat à utiliser, et donc l'instance ne saisit pas.

Pour corriger cela, vous pouvez ajouter une contrainte équationnelle à dire que TupleFn est correct. Malheureusement, étant donné que la contrainte doit mentionner le type out, vous devez l'inclure en tant que paramètre de type supplémentaire dans la classe. Au moins, ce qui suit semble fonctionner (testé avec GHC 7.8 seulement):

{-# LANGUAGE TypeFamilies, FlexibleInstances, 
      MultiParamTypeClasses, 
      OverlappingInstances #-} 

type family TupleFn ty out where 
    TupleFn (a,b) output = a -> (TupleFn b output) 
    TupleFn b output = b -> output 

class ApplyFnToTuple a out where 
    applyFnToTuple :: a -> TupleFn a out -> out 

instance ApplyFnToTuple b out => ApplyFnToTuple (a,b) out where 
    applyFnToTuple (a,b) fn = applyFnToTuple b (fn a) 

instance TupleFn a out ~ (a -> out) => ApplyFnToTuple a out where 
    applyFnToTuple b fn = fn b 

Answer 2

Comme d'habitude, vous pouvez le faire avec singletons et tapez les familles:

{-# LANGUAGE GADTs, DataKinds, TypeFamilies, TypeOperators #-} 

type family Tuple b as where 
    Tuple b '[]  = b 
    Tuple b (a ': as) = (b, Tuple a as) 

type family Function as b where 
    Function '[]  b = b 
    Function (a ': as) b = a -> Function as b 

data SingList as where 
    SNil :: SingList '[] 
    SCons :: SingList as -> SingList (a ': as) 

applyToTuple :: SingList as -> Tuple a as -> Function (a ': as) b -> b 
applyToTuple SNil  x  f = f x 
applyToTuple (SCons as) (x, xs) f = applyToTuple as xs (f x) 

main = do 
    print $ applyToTuple (SCons (SCons SNil)) ('o',('t','w')) $ \a b c -> [a,b,c] == "otw" 
    print $ applyToTuple (SCons SNil)   ('h','i') $ \a b -> [a,b] == "hi" 
    print $ applyToTuple (SCons (SCons SNil)) ("hello",('y','o')) $ \a b c -> a ++ [b,c] 

Tuple a [b, c, d] réduit à (a, (b, (c, d))).

Function [a, b, c, d] r se réduit à a -> b -> c -> d -> r.

Par conséquent, si as == [b, c, d], puis

Tuple a as -> Function (a ': as) r -> r 

réduit à

(a, (b, (c, d))) -> (a -> b -> c -> d -> r) -> r 

Answer 3

Ma solution éventuelle, pour toute personne qui trouve cette question:

Comme DanielWagner suggéré, je fini par préférer le légèrement modifié mise en forme (using() à la fin d'une chaîne de tuple pour signifier finish). Cela en fait assez simple comme ceci:

type family TupleFn ty out where 
    TupleFn() output = output 
    TupleFn (a,b) output = a -> (TupleFn b output) 

class ApplyFnToTuple a where 
    applyFnToTuple :: a -> TupleFn a out -> out 

instance ApplyFnToTuple b => ApplyFnToTuple (a,b) where 
    applyFnToTuple (a,b) fn = applyFnToTuple b (fn a) 

instance ApplyFnToTuple() where 
    applyFnToTuple _ fn = fn 

et cela peut être utilisé comme:

applyFnToTuple ('a',('b',())) $ \a b -> [a,b] == "ab" 
applyFnToTuple ("hello",(12,('r',()))) $ \h n r -> h ++ show n ++ [r] == "hello12r" 

J'espère que les instances peuvent être peaufiné; ce n'était que le premier que j'ai essayé que GHC aimait :)

L'approche d'Ørjan Johansen (voir sa réponse) est un peu plus compliquée mais offre un cas final encore plus soigné!

En note, lorsque j'ai voulu traduire une structure en une fonction correspondante, j'ai fini par utiliser mon propre type de données pour la puissance supplémentaire qu'il me donne. La forme la plus simple de ce que je peux venir avec (ne pas utiliser DataKinds pour l'instant) à utiliser comme exemple:

--using DataKinds these could be done slightly neater: 
data Cons a b 
data Nil 

-- the list itself, where the type 'a' is built from the above tags 
data MyList a where 
    LCons :: itemty -> MyList a -> MyList (Cons itemty a) 
    LNil :: MyList Nil 

-- this type family converts that type 'a' to a function signature. 
type family MyListFn a output where 
    MyListFn (Cons a b) output = a -> (MyListFn b output) 
    MyListFn Nil output = output 

-- this function applies items in MyList a to a MyListFn a just 
-- like we did with tuples. Note no type family, because 
-- no type dependant differences in behaviour needed: 
applyFnToMyList :: MyList a -> MyListFn a out -> out 
applyFnToMyList (LCons a b) fn = applyFnToMyList b (fn a) 
applyFnToMyList LNil fn = fn 

avec une utilisation très similaire tuple cas:

applyFnToMyList (LCons 'a' (LCons 'b' LNil)) $ \a b -> [a,b] == "ab" 
applyFnToMyList (LCons "hello" (LCons 12 (LCons 'r' LNil))) $ \h n r -> h ++ show n ++ [r] == "hello12r" 

TL; DR Vous pouvez créer des fonctions qui appliquent une fonction de n'importe quelle parité requise sur certains éléments d'une structure de données polymorphique de manière totalement sécurisée. Des trucs géniaux, Haskell!