Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does haskell keep track of function composition?

I was wondering if Haskell keeps track of weather a function is a function composition, i.e would it be possible for me to define a function that does something similar to this?:

compositionSplit f.g = (f,g)
like image 915
MYV Avatar asked May 29 '13 23:05

MYV


People also ask

Is Haskell right or left associative?

Nevertheless function composition in Haskell is right associative: infixr 9 .

What does map do in Haskell?

map takes a function and a list and applies that function to every element in the list, producing a new list.

What does flip do Haskell?

flip f takes its (first) two arguments in the reverse order of f. flip the order of the first two arguments of a function.

How are higher order functions used in Haskell?

In Haskell, a function that can take other functions as arguments or return functions is called a higher-order function. These are particularly useful in that they allow us to create new functions on top of the ones we already have, by passing functions as arguments to other functions.


2 Answers

No, it wouldn't be possible.

For example,

f1 = (+ 1) . (+ 1) :: Int -> Int

is the same function as

f2 = subtract 1 . (+ 3) :: Int -> Int

and referential transparency demands that equals can be substituted for equals, so if compositionSplit were possible, it would

  • need to produce the same result for f1 and f2, since that is the same function, yet
  • compositionSplit f1 = ((+ 1), (+1)) and compositionSplit f2 = (subtract 1, (+ 3)) would be required by the specification of compositionSplit.
like image 100
Daniel Fischer Avatar answered Oct 23 '22 08:10

Daniel Fischer


It could. In strictly interpretational non-compiled implementation, you could represent functions as

data Function = F Source | Compo Function Function

and then you'd just define

compositionSplit (Compo f g) = Just (f,g)
compositionSplit _  = Nothing

Such implementation would treat function equality (w.r.t. referential transparency) as intensional, not extensional equality. As the language itself doesn't say anything about equality of functions AFAIK, this shouldn't affect anything (except maybe performance).

In compiled implementations this could be achieved too, e.g. by maintaining provenance for every object in memory.


AndrewC gives a winning counter-argument: for the two values a=f.(g.h) and b=(f.g).h, if we want to consider them as equal values - which we normally do, in Haskell - fst.unJust.deCompo will produce two different results, breaking referential transparency. So it can't be part of pure FP paradigm. It'd have to return something which we could legitimately consider as being equal values too, in the two cases, and we wouldn't be able to take it apart, without breaking the purity. Maybe such a thing could exist in some impure monad, but that's not what OP asked for, sadly. :) So this answer is in error.

like image 40
Will Ness Avatar answered Oct 23 '22 09:10

Will Ness