7

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)
MYV
  • 4,294
  • 6
  • 28
  • 24
  • 4
    If you want to keep track of the intermediate functions in a composition, you can use a [Thrist](http://hackage.haskell.org/package/thrist). They were [invented](http://omega.googlecode.com/files/Thrist-draft-2011-11-20.pdf) exactly for this purpose. – phipsgabler May 30 '13 at 10:21

2 Answers2

18

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.
Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • Thanks, but I dont understand your statement about refrential transparency – MYV May 29 '13 at 23:42
  • 2
    Referential transparency is explained [here](http://stackoverflow.com/questions/210835/what-is-referential-transparency) and [on wikipedia](http://en.wikipedia.org/wiki/Referential_transparency_%28computer_science%29) for example. It basically means that you can substitute an expression with one with the same meaning without changing the result in this context. Since `f1` and `f2` are the same function, they can't be distinguished by any function. – Daniel Fischer May 29 '13 at 23:53
  • 3
    @Maksim: Referential transparency implies (among other things) that functions behave as mathematical functions. That is, whenever `x = y` then also `f x = f y`. Observe that `f1` and `f2` are equal, therefore `compositionSplit f1` should be equal to `compositionSplit f2`, but it isn't! – Vitus May 29 '13 at 23:53
  • 2
    @Vitus depends on how you define *equality* for functions. `(\x.x+2)` and `(\x.x+1+1)` are only [*extensionally* equal functions](http://en.wikipedia.org/wiki/Extensionality). In a language with intensional equality we could distinguish between the two. (just carry around the source code, and simplification/compilation steps, together with the compiled function object in memory -- *"provenance"*). – Will Ness May 30 '13 at 08:13
  • @Vitus both your statements, A="Observe that `f1` and `f2` are equal," and B="`compositionSplit f1` isn't equal to `compositionSplit f2`!", are entirely POV-dependent (let `compositionSplit` produce `FuncPair (f,g)` and treat their equality specially). I.e. I can refute your argument by treating any of the two statements as false, by redefining what "equal" means in each case. -- IOW referential transparency demands that equals - *as understood by a language* - be substitutable for equals, and *the Haskell language* doesn't define equality for functions AFAIK. – Will Ness May 30 '13 at 09:29
  • @WillNess: Indeed, I agree. I was merely trying to explain the point Daniel made. I guess the wording could have been better, though. – Vitus May 30 '13 at 13:10
  • @Vitus in my mind, when I wrote it, "your" in "your argument" was decidedly un-emphasized. :) Was thinking more about the argument itself. I could've used "that" too (and be a bit less verbose, I guess). – Will Ness May 30 '13 at 14:07
  • @WillNess `==` isn't defined for functions, but referential transparency concerns `=` arguably more than it does `==`. In fact, referential transparency concerns = more than `=`. It's about being able to substitute `x` wherever something that = `x` is, not just wherever it `(== x)`. You can't argue yourself out of referential transparency by the absence of an `Eq` instance! Pascal has no `Eq` instances; is it referentially transparent? No! – AndrewC May 30 '13 at 14:41
  • @AndrewC `(1+).(1+)` is certainly not = `(+0).(+2)`. We don't need Eq instances for that. So even more so, the argument that these two *must* somehow produce same decomposition because they are somehow "same" doesn't stand. – Will Ness May 30 '13 at 14:44
  • @WillNess You say that Vitus's statements are POV-dependant, and do a quick gear change in your own statement to "in a language with intensional equality" - that language is not called Haskell; it's OK to be POV-dependent when the POV is Haskell, and the question's tagged Haskell. I agree it's theoretically possible, and you can even implement some sort of audit-keeping composition operator, but it won't be the `.` referred to in the question, nor will it be able to decompose `(+1).(+1)` unless you hide `.` from the Prelude and replace it. – AndrewC May 30 '13 at 14:44
  • @AndrewC I think `(.)` *could* be defined that way, and it would be perfectly normal part of Haskell. It wouldn't disturb anything, I think. My presentation could be flawed, that is possible. – Will Ness May 30 '13 at 14:45
  • @AndrewC I just said that it *could* be defined that way, in a compliant implementation. GHC the compiler is not Haskell the language. – Will Ness May 30 '13 at 14:48
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/30920/discussion-between-andrewc-and-will-ness) – AndrewC May 30 '13 at 14:49
  • 3
    I perhaps put my point best when I said you want `(.)` and `id` to be a monoid, i.e. `f.(g.h)` = `(f.g).h` and `id.f` = `f`. You can't have referential transparency, this monoid and a decomposition operator. If you don't have this, you're not doing pure functional programming. It's not impossible, it's just not f.p.. – AndrewC May 30 '13 at 17:18
  • @AndrewC yes, this is the winning argument. it's not a part of pure FP, if we want to consider `f.(g.h)` and `(f.g).h` as the same function. Maybe it could be a part of some impure monad?... – Will Ness May 30 '13 at 18:02
4

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Thanks. what does "Source" refer to in the above data declaration? When I type in the data declaration you provided, the computer tells me Source is undeclared. – MYV May 30 '13 at 20:55
  • @Maksim no, it was all hypothetical, an imagined interpreter that you would have to write for yourself to achieve that. And it turned out to be an impure feature. Disregard please. :) – Will Ness May 31 '13 at 05:10