Fonction a -> b -> (a -> b) la plus courte dans Haskell

19

J'ai reçu la question suivante lors d'un test:

Écrivez une fonction favec le type suivant a -> b -> (a -> b). aet bne doit en aucun cas être lié, plus le code est court, mieux c'est.

Je suis venu avec f a b = \x -> snd ([a,x],b). Pouvez-vous trouver quelque chose de plus petit?

Actuellement, le gagnant est: f _=(.f).const

code-golf functional-programming haskell Radu Stoenescu
la source
Si un type plus général est autorisé: f = const const.
hammar
@hammar: ou f _ b _ = b, mais, étant donné la solution de la question, je soupçonne qu'un type plus général n'est pas autorisé.
Tikhon Jelvis
6
Si un type plus général est autorisé, pourquoi pas f = id?
Tom Ellis
7
En fait, si un type plus général est autorisé, f = fc'est une solution, donc je suppose que les conditions sur le type sont très importantes!
Tom Ellis
2
Un type plus général n'est pas autorisé, vos hypothèses étaient correctes.
Radu Stoenescu

Réponses:

11

Votre exemple peut être réduit en supprimant la fonction anonyme sur le côté droit:

f a b x = snd ([a,x],b)

Cela fonctionne parce que le type a -> b -> a -> best équivalent à a -> b -> (a -> b)Haskell.

Matt Fenwick
la source
4
Modification légèrement plus courte:f a b x = snd (f x,b)
Ed'ka
5

La fonction f _=(.f).constest en fait d'un type plus général que f :: a -> b -> (a -> b), à savoir f :: a -> b -> (c -> b). Si aucune signature de type n'est donnée, le système d'inférence de type déduit un type de f :: a -> b -> (a -> b), mais si vous incluez la signature de type f :: a -> b -> (c -> b)avec la même définition exacte, Haskell la compilera sans problème et signalera des types cohérents pour les applications partielles de f. Il y a probablement une raison profonde pour laquelle le système d'inférence de type est plus strict que le système de vérification de type dans ce cas, mais je ne comprends pas assez la théorie des catégories pour trouver une raison pour laquelle cela devrait être le cas. Si vous n'êtes pas convaincu, vous êtes invités à l'essayer vous-même.

archaephyrryx
la source
pourrait être comme le cas de f a b = f a a. il en déduit être de type a -> a -> bbien qu'il soit conforme au type a -> b -> c. c'est parce que si fon ne lui donne pas de type, il ne peut s'utiliser que de façon monomorphe.
fier haskeller
je ne pense pas que cela devrait être important
fier haskeller
4

Étant donné ScopedTypeVariables, je suis venu avec ceci:

f (_::a) b (_::a) = b

Si vous rétrécissez à la fois ma fonction et la vôtre, la mienne est un poil plus court:

f(_::a)b(_::a)=b
f a b x=snd([a,x],b)

Bien sûr, vous n'êtes probablement pas autorisé à vous fier à ScopedTypeVariables: P.

Tikhon Jelvis
la source
3
Ce n'est pas aussi court que f _=(.f).const(en raison de Sassa NF ). Qui n'a pas non plus besoin ScopedTypeVariables.
cessé de tourner dans le sens inverse des aiguilles d'une montre le
Hmm, j'ai d'abord pensé que cela nécessiterait que les premier et troisième arguments soient des listes ...
Chris Taylor
@ChrisTaylor: Trop d'OCaml en tête? :)
Tikhon Jelvis
Hah, ça doit être! ;)
Chris Taylor