Writing in pointfree style f x = g x x
Pergunta
I am learning Haskell. I'm sorry for asking a very basic question but I cant seem to find the answer. I have a function f defined by :
f x = g x x
where g is an already defined function of 2 arguments. How do I write this pointfree style? Edit : without using a lambda expression.
Thanks
Solução
f
can be written with Control.Monad.join
:
f = join g
join
on the function monad is one of the primitives used when constructing point-free expressions, as it cannot be defined in a point-free style itself (its SKI calculus equivalent, .SII
— ap id id
in Haskell — doesn't type)
Outras dicas
This is known as "W" combinator:
import Control.Monad
import Control.Monad.Instances
import Control.Applicative
f = join g -- = Wg (also, join = (id =<<))
= (g `ap` id) -- \x -> g x (id x) = SgI
= (<*> id) g -- = CSIg
= g =<< id -- \x -> g (id x) x
= id =<< g -- \x -> id (g x) x
S,K,I are one basic set of combinators; B,C,K,W are another - you've got to stop somewhere (re: your "no lambda expression" comment):
_B = (.) -- _B f g x = f (g x) = S(KS)K
_C = flip -- _C f x y = f y x = S(S(K(S(KS)K))S)(KK)
_K = const -- _K x y = x
_W = join -- _W f x = f x x = CSI = SS(KI) = SS(SK)
_S = ap -- _S f g x = f x (g x) = B(B(BW)C)(BB) = B(BW)(BBC)
= (<*>) -- from Control.Applicative
_I = id -- _I x = x = WK = SKK = SKS = SK(...)
{-
Wgx = gxx
= SgIx = CSIgx
= Sg(KIg)x = SS(KI)gx
= gx(Kx(gx)) = gx(SKgx) = Sg(SKg)x = SS(SK)gx
-- _W (,) 5 = (5,5)
-- _S _I _I x = x x = _omega x -- self-application, untypeable
-}
I got here by pure chance, and I want to offer my solution, as nobody has mentioned lifting yet in this thread, not explicitly at least.
This is a solution:
f = liftM2 g id id
How to look at it?
g
has typea -> a -> b
, i.e. it takes two values of some type (the same type for both, otherwise the definition the OP gave off
wouldn't make sense), and gives back another value of some type (not necessarily of the same type as the arguments);lift2M g
is the lifted version ofg
and it has type(Monad m) => m a -> m a -> m b
: it takes two monadic values, which are each a value in a so-far-unspecified context, and gives back a monadic value;when passing two functions to
liftM2 g
, the die is cast on what the context of theMonad
is: it is that the values are not in there yet, but will eventually be, when the function will receive the arguments it needs; in other words, functions are monads that store their own future values; therefore,lift2M g
takes in input two functions (or, the future values of two functions), and gives back the another function (or, its future value); knowing this, its type is the same as above if you changem
to(->) r
, orr ->
:(r -> a) -> (r -> a) -> (r -> b)
the two functions that we pass are both
id
, which promises it'll give back the same value it receives;liftM2 g id id
is therefore a function of typer -> b
that passes its argument to those twoid
s, which let it unchanged and forward it tog
.
In a similar fashion, one can exploit that functions are applicative functors, and use this solution:
f = g <$> id <*> id