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

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