Search code examples
haskellsyntaxfunctional-programmingpointfreetype-constructor

Point-free function to add 2 elements to the list / double application of (:) list data constructor and (.)


I am struggling to define correctly the point-free version of the function, which adds 2 elements to the list.

It is easy to come up with a number of straightforward trivial implmentations:

addTwoElems :: a -> a -> [a] -> [a]

addTwoElems x y xs = x : y : xs
addTwoElems x y    = (++) [x, y]
addTwoElems        = (.) `on` (:)  “ point free but with additional function

But how would a point-free composition (.) of the two list data constructors (:) look like?

Please not just show the correct function implementation, but please with explanations of the steps and logic behind how to come to the right version.


Solution

  • Per the comments, a step-by-step derivation that only uses . and ::

    addTwoElems x y xs = x : y : xs
    -- rewrite the first : as a prefix function
    addTwoElems x y xs = (:) x (y : xs)
    -- rewrite the second : as a prefix function
    addTwoElems x y xs = (:) x ((:) y xs)
    -- use function composition to get xs out of the parentheses
    addTwoElems x y xs = ((:) x . (:) y) xs
    -- eta-reduce to get rid of xs
    addTwoElems x y = (:) x . (:) y
    -- rewrite the . as a prefix function
    addTwoElems x y = (.) ((:) x) ((:) y)
    -- use function composition to get y out of the parentheses
    addTwoElems x y = ((.) ((:) x) . (:)) y
    -- eta-reduce to get rid of y
    addTwoElems x = (.) ((:) x) . (:)
    -- rewrite the second . as an operator section, so that the part of the expression with x is last
    addTwoElems x = (. (:)) ((.) ((:) x))
    -- use function composition to get x out of the inner parentheses
    addTwoElems x = (. (:)) (((.) . (:)) x)
    -- use function composition to get x out of the outer parentheses
    addTwoElems x = ((. (:)) . (.) . (:)) x
    -- eta-reduce to get rid of x
    addTwoElems = (. (:)) . (.) . (:)