Najkrótsza funkcja a -> b -> (a -> b) w Haskell

19

Podczas testu dostałem następujące pytanie:

Napisz funkcję fo następującym typie a -> b -> (a -> b). ai bnie powinien być w żaden sposób związany, im krótszy kod, tym lepiej.

Wymyśliłem f a b = \x -> snd ([a,x],b). Czy możesz znaleźć coś mniejszego?

Obecnie zwycięzcą jest: f _=(.f).const

code-golf functional-programming haskell Radu Stoenescu
źródło
Jeśli bardziej ogólny typ jest dozwolona: f = const const.
hammar
@hammar: albo f _ b _ = b, ale, biorąc pod uwagę rozwiązanie w kwestii, podejrzewam bardziej ogólny typ jest nie dozwolone.
Tikhon Jelvis
6
Jeśli dopuszcza się bardziej ogólny typ, dlaczego nie f = id?
Tom Ellis
7
W rzeczywistości, jeśli dozwolony jest bardziej ogólny typ, jest f = fto rozwiązanie, więc myślę, że warunki na typie są bardzo ważne!
Tom Ellis
2
Bardziej ogólny typ jest niedozwolony, twoje założenia były prawidłowe.
Radu Stoenescu

Odpowiedzi:

11

Twój przykład można zmniejszyć, pozbywając się anonimowej funkcji po prawej stronie:

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

Działa to, ponieważ typ a -> b -> a -> bjest równoważny z a -> b -> (a -> b)Haskell.

Matt Fenwick
źródło
4
Nieco krótsza modyfikacja:f a b x = snd (f x,b)
Ed'ka
5

Ta funkcja f _=(.f).constjest w rzeczywistości bardziej ogólna niż f :: a -> b -> (a -> b)mianowicie f :: a -> b -> (c -> b). Jeśli nie zostanie podany podpis typu, system wnioskowania o typ wyszuka typ f :: a -> b -> (a -> b), ale jeśli podasz podpis typu f :: a -> b -> (c -> b)z dokładnie taką samą definicją, Haskell skompiluje go bez problemu i zgłosi spójne typy dla częściowych zastosowań f. Prawdopodobnie istnieje jakiś głęboki powód, dla którego system wnioskowania typu jest bardziej rygorystyczny niż system sprawdzania typu w tym przypadku, ale nie rozumiem wystarczającej teorii kategorii, aby wymyślić powód, dla którego tak powinno być. Jeśli nie jesteś przekonany, możesz spróbować samemu.

archaephyrryx
źródło
może być jak w przypadku f a b = f a a. wydaje się być typem, a -> a -> bchociaż jest zgodny z typem a -> b -> c. Dzieje się tak, ponieważ jeśli fnie zostanie podany typ, może używać się tylko monomorficznie.
dumny haskeller
nie sądzę, że to powinno mieć znaczenie
dumny haskeller
4

Dany ScopedTypeVariables , wpadłem na to:

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

Jeśli zmniejszysz zarówno moją funkcję, jak i twoją, moja będzie o włos krótsza:

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

Oczywiście prawdopodobnie nie możesz polegać na ScopedTypeVariables: P.

Tikhon Jelvis
źródło
3
To nie jest tak krótkie jak f _=(.f).const(z powodu Sassa NF ). Co też nie potrzebuje ScopedTypeVariables.
przestał się obracać przeciwnie do zegara
Hmm, początkowo myślałem, że będzie to wymagało pierwszego i trzeciego argumentu, aby to były listy ...
Chris Taylor
@ChrisTaylor: Za dużo OCaml w umyśle? :)
Tikhon Jelvis
Hah, musi być! ;)
Chris Taylor