Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does this point free definition not work in Haskell?

I tried to make the following function definition:

relativelyPrime x y = gcd x y == 1

point-free:

relativelyPrime = (== 1) . gcd

However, this gives me the following error:

Couldn't match type ‘Bool’ with ‘a -> Bool’
Expected type: (a -> a) -> a -> Bool
  Actual type: (a -> a) -> Bool
Relevant bindings include
  relativelyPrime :: a -> a -> Bool (bound at 1.hs:20:1)
In the first argument of ‘(.)’, namely ‘(== 1)’
In the expression: (== 1) . gcd
In an equation for ‘relativelyPrime’:
    relativelyPrime = (== 1) . gcd

I don't quite understand. gcd takes two Ints/Integer, returns one Ints/Integer, then that one Int/Integer is checked for equality to '1'. I don't see where my error is.

like image 220
Ben Avatar asked Oct 11 '15 19:10

Ben


People also ask

What is point free Haskell?

So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values. In the declaration. f x = x + 1. we define the function f in terms of its action on an arbitrary point x .

What is the point of point free code?

Tacit programming, also called point-free style, is a programming paradigm in which function definitions do not identify the arguments (or "points") on which they operate. Instead the definitions merely compose other functions, among which are combinators that manipulate the arguments.

What does () mean in Haskell?

() is very often used as the result of something that has no interesting result. For example, an IO action that is supposed to perform some I/O and terminate without producing a result will typically have type IO () .

What does NS mean in Haskell?

The sequence (n:ns) is a shorthand for head - tail. Quite literally, the first value, the head, is called n and the remained are the other, potentially plural, n s, which is why it is called ns . Haskell has pattern matching.


2 Answers

It doesn't work because gcd requires two inputs whereas function composition only provides gcd one input. Consider the definition of function composition:

f . g = \x -> f (g x)

Hence, the expression (== 1) . gcd is equivalent to:

\x -> (== 1) (gcd x)

This is not what you want. You want:

\x y -> (== 1) (gcd x y)

You could define a new operator to compose a unary function with a binary function:

f .: g = \x y -> f (g x y)

Then, your expression becomes:

relativelyPrime = (== 1) .: gcd

In fact, the (.:) operator can be defined in terms of function composition:

(.:) = (.) . (.)

It looks kind of like an owl, but they are indeed equivalent. Thus, another way to write the expression:

relativelyPrime = ((== 1) .) . gcd

If you want to understand what's happening then see: What does (f .) . g mean in Haskell?

like image 167
Aadit M Shah Avatar answered Nov 15 '22 06:11

Aadit M Shah


as you commented on it - if you really want a point-free version you can first use uncurry gcd to transform gcd into a version that accepts a single input (a tuple):

Prelude> :t uncurry gcd
uncurry gcd :: Integral c => (c, c) -> c

then check with (== 1) and finally curry it again for the original signature:

relativeelyPrime = curry ((== 1) . (uncurry gcd))

your version did not work just because gcd produces a function if given only the first argument and this is no legal input for (== 1) which awaits a number.

like image 40
Random Dev Avatar answered Nov 15 '22 07:11

Random Dev