Kürzeste a -> b -> (a -> b) -Funktion in Haskell

19

Bei einem Test habe ich folgende Frage bekommen:

Schreiben Sie eine Funktion fmit folgendem Typ a -> b -> (a -> b). aund bsollte in keiner Weise gebunden sein, je kürzer der Code, desto besser.

Ich habe es mir ausgedacht f a b = \x -> snd ([a,x],b). Kannst du etwas winzigeres finden?

Derzeit ist der Gewinner: f _=(.f).const

code-golf functional-programming haskell Radu Stoenescu
quelle
Wenn ein allgemeinerer Art ist erlaubt: f = const const.
Hammar
@ Hammar: oder f _ b _ = b, aber angesichts der Lösung in der Frage, ich vermute, ein allgemeinerer Typ ist nicht zulässig.
Tikhon Jelvis
6
Wenn ein allgemeinerer Typ zulässig ist, warum nicht f = id?
Tom Ellis
7
In der Tat, wenn ein allgemeinerer Typ erlaubt ist, dann f = fist eine Lösung, also denke ich, dass die Bedingungen für den Typ sehr wichtig sind!
Tom Ellis
2
Ein allgemeinerer Typ ist nicht zulässig, da Ihre Annahmen korrekt waren.
Radu Stoenescu

Antworten:

11

Ihr Beispiel kann verkleinert werden, indem Sie die anonyme Funktion auf der rechten Seite entfernen:

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

Dies funktioniert, weil der Typ a -> b -> a -> bdem a -> b -> (a -> b)in Haskell entspricht.

Matt Fenwick
quelle
4
Etwas kürzere Änderung:f a b x = snd (f x,b)
Ed'ka
5

Die Funktion f _=(.f).constist eigentlich allgemeiner als f :: a -> b -> (a -> b), nämlich f :: a -> b -> (c -> b). Wenn keine Typensignatur angegeben ist, leitet das Typinferenzsystem einen Typ von ab f :: a -> b -> (a -> b). Wenn Sie jedoch die Typensignatur f :: a -> b -> (c -> b)mit genau derselben Definition einfügen, kompiliert Haskell sie ohne Probleme und gibt konsistente Typen für die Teilanwendungen von f aus. Es gibt wahrscheinlich einen tiefen Grund, warum das Typinferenzsystem in diesem Fall strenger ist als das Typprüfsystem, aber ich verstehe nicht genug Kategorietheorie, um einen Grund dafür zu finden, warum dies der Fall sein sollte. Wenn Sie nicht überzeugt sind, können Sie es gerne selbst versuchen.

Archaephyrryx
quelle
könnte wie der Fall sein f a b = f a a. es folgt daraus, dass es vom Typ ist, a -> a -> bobwohl es dem Typ entspricht a -> b -> c. es liegt daran, dass fes sich nur monomorph verwenden kann, wenn es keinen Typ erhält.
stolzer Haskeller
Ich denke nicht, dass das eine Rolle spielen sollte
stolzer Haskeller
4

In Anbetracht ScopedTypeVariables, kam ich mit auf den Punkt :

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

Wenn Sie sowohl meine als auch Ihre Funktion einschränken, ist meine Haarlänge kürzer:

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

Natürlich dürfen Sie sich wahrscheinlich nicht auf Folgendes verlassen ScopedTypeVariables: P.

Tikhon Jelvis
quelle
3
Dies ist nicht so kurz wie f _=(.f).const ( aufgrund von Sassa NF ). Welches braucht auch nicht ScopedTypeVariables.
aufgehört, sich
Hmm, ich dachte zunächst, dass das erste und dritte Argument Listen sein müssten ...
Chris Taylor,
@ ChrisTaylor: Zu viel OCaml im Kopf? :)
Tikhon Jelvis
Hah, muss sein! ;)
Chris Taylor