3

I want to know if it is possible to convert a recursive function into point free definition.

If we take an easy recursive function.

factorial :: int-> int
factorial 0=1
factorial n+1= (n+1) *factorial n

IF we have non recursive def.

factorial :: int-> int
factorial n= product [1..n]  
   <=> factorial n = product.enumFromTo 1 n 
   <=> factorial   = product.enumFromTo 1  

But how can i do the same on the recursive definition?

Reason why i am asking is that i want to make transformationsApply pointfree.

transformationsApply :: Eq a => a -> ([a] -> [a]) -> [([a], [a])] -> [a] -> Maybe [a]
transformationsApply _ _ [] _= Nothing
transformationsApply wc func ((a,b):xs) (y:ys)
   = orElse (transformationApply wc func (y:ys) (a,b)) 
            (transformationsApply wc func xs (y:ys))

transformationApply used above is defined as

transformationApply :: Eq a => a -> (([a] -> [a]) -> ([a] -> (([a], [a]) -> Maybe [a])))

transformationApply wc func xs (a,b) 
   = mmap ((substitute wc b).func) (match wc a xs)
2
  • 6
    Its better to keep your code readable than to write some complex pointfree form.
    – Satvik
    Nov 10, 2013 at 9:55
  • what (type) is orelse? substitute? mmap? match?
    – Will Ness
    Nov 10, 2013 at 10:22

4 Answers 4

5

I would suggest to keep your code more readable than to try converting it to incomprehensible pointfree form.

The easiest way to convert a function to pointfree form is to ask lambdabot. Now when you have recursive function you can convert that to non-recursive using fix. Here is the example of fact function (A direct conversion from what lambdabot gave) and you can see how readable it is.

import Control.Monad
import Data.Function


if' :: Bool -> a -> a -> a
if' True  x _ = x
if' False _ y = y

fact = fix $ ap (flip if' 1 . (0 ==)) . ap (*) . (. subtract 1)
2
  • Or cabal install pointfree and use pointfree directly. I don’t find the converted version so unpleasant in this case. flip if' 1 sets the then case, (0 ==) is the (partially applied) condition, (. subtract 1) is selecting the second argument and subtracting one from it, and ap (*) is recurring with the first argument and combining the results with (*).
    – Jon Purdy
    Nov 10, 2013 at 10:10
  • @JonPurdy Yes, But I am not sure how you convert pattern matching to pointfree. This will require an additional Eq constraint.
    – Satvik
    Nov 10, 2013 at 10:32
1

While you can convert most recursive functions to point free form in an automatic manner, the result is likely to be ugly and rather useless, as others have shown.

However what you have here is not really a general recursion. You have a fold on a list, building up a result from applying a function to each list element and then combining them.

Haskell has building blocks for folding and otherwise recursing on lists specifically, which will give a much prettier result. (Although you still need to use your judgement of whether it is an improvement.) The most common such building blocks are the functions foldr and map. In fact your example can be rewritten as:

transformationsApply :: Eq a => a -> ([a] -> [a]) -> [([a], [a])] -> [a] -> Maybe [a]
transformationsApply wc func xs (y:ys) =
    foldr orElse Nothing (map (transformationApply wc func (y:ys)) xs)
transformationsApply _ _ [] [] = Nothing

(The last line is because of a corner case: your original function checks if the last argument is empty in all cases except when the xs list is. Maybe you don't need this.)

1

starting with factorial, first we'll need a type case discriminator, to encapsulate the pattern matching on numbers for us,

num :: (Num a) => b -> (a -> b) -> a -> b
num z _  0 = z
num _ nz x = nz x

now, using the identity (g =<< f) x = g (f x) x, we write

import Control.Applicative
import Data.Function (fix)

fact :: (Num c, Enum c) => c -> c
fact = num 1 ((*) =<< (fact.pred))

To get the truly pointfree form of it we need to push fact to the right, and fix it:

     = num 1 . ((*) =<<) . (.pred) $ fact
     = fix (num 1 . ((*) =<<) . (.pred))

proceeding to your 2nd function, as Ørjan Johansen points out it is essentially a right fold (if we ignore the intricacies of the forcing order for arguments, as determined by the explicit patterns that you use):

transformationsApply :: Eq a => a -> ([a] -> [a]) -> [([a], [a])] -> [a] -> Maybe [a]
transformationsApply a b c d
   = foldr (orElse . transformationApply a b d) Nothing c

which already looks quite combinatory. So here recursion is encapsulated by foldr, instead of being explicitly expressed by fix.

We could juggle some more for the arguments order, but that's much less fun:

   = flip (foldr . (orElse .) . transformationApply a b) Nothing d c
   = flip (flip (foldr . (orElse .) . transformationApply a b) Nothing) c d
   = ...
0

We'll need an inline branching operation, while

if' True  t _ = t
if' False _ e = e

is popular another form is more useful. I'll call it p

p check a | check a   = Right a
          | otherwise = Left  a

which is powerful enough to define if'

if' b t e = either (const e) (const t) . p (const b)

but has the nicer property

(\a -> if' (check a) (t a) (e a)) == either e t . p check

and it lets us get rid of the first branch in factorial

factorial' = either (const 1) (\n -> n * factorial (n-1)) . p (==0)

which means we just need to somehow eliminate the (\n -> n * factorial (n-1)) bit. Using the (&&&) "fanout" combinator from Control.Arrow

(&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))

we have

(\n -> n * factorial (n-1)) == uncurry (*) . (id &&& factorial . (+ negate 1))

which is a bit annoying due to (-) sectioning ambiguity. I'll leave it for now, though so that our final function is

factorial'' :: Int -> Int
factorial'' = 
  either (const 1) 
         (uncurry (*) 
          . (id &&& factorial'' . (+ negate 1))) 
  . p (==0)

and the recursive part of the definition works just fine. Technically the type is more general than that

factorial'' :: (Eq a, Num a) => a -> a

which is perhaps a little unsatisfying since we need the Eq constraint now while the pattern-matching version does not. We could do better if our numbers had natural destructors available to us. For instance, if we define our own naturals with "natural" constructors and destructors

data Nat = Z | S Nat

cons :: Maybe Nat -> Nat
cons Nothing  = Z
cons (Just n) = S n

uncons :: Nat -> Maybe Nat
uncons Z     = Nothing
uncons (S n) = Just n

We can do all the rest without further pattern matching. Let's get a plus and a mult

--  Z   + n = n
--  S m + n = S (m + n)    
plus n = maybe n (S . plus n) . uncons

--  Z   * n = Z
--  S m * n = n + (m * n)
mult n = maybe Z (plus n . mult n) . uncons

And with these we have

naturalFact :: Nat -> Nat
naturalFact = maybe (S Z) (uncurry mult . (S &&& naturalFact)) . uncons

which is pretty satisfying. It's probably as satisfying as you can get without eliminating the recursive step and entering the Squiggol style of pointfree programming entirely or Church-encoding all of our pattern matches away entirely.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.