CODEWITHSUNDEEP
haskelllambdacalculus
vladfau
vladfau

Reputation: 1003

Can't properly understand lambdas in Haskell

I have following code, implmenting inverse function calculation, basing on this formulas:

enter image description here

enter image description here

derivation :: (Fractional a) => (a -> a) -> (a -> a)
derivation f = \ x -> ( ( f (x + dx) - f (x) ) / dx ) where dx = 0.1

evalA k f
  | k == 0 =  \x -> x
  | otherwise = \x -> (derivation (evalA (k-1) f) x) / (derivation f x)

inverseFun f x =
 let
   x0 = 3.0
   eps = 0.001
   iter k prev sum =
    let       
      elemA = evalA k f x0
      elemB = prev * (x - (f x0)) / (if k == 0 then 1 else k)
      newItem = elemA * elemB
    in
      if abs (newItem) < eps
      then sum
      else iter (k + 1) elemB (sum + newItem)
  in
    iter 0 1.0 0.0


f1 = \x -> 1.0 * x * x

main = do
  print $ inverseFun f1 2.5

I need to optimise it by moving evalA inside the inverseFun and store previous step calculation A'n/F' to reuse it on the next iteration, if possible. As far as I understand, each time evalA returns some sort of function and x applies afterwards, right before declaring elemA.

How can I convert my evalA or rewrite it to store previous results (by passing these results in iter, obviously)?

Don't mind if this calculations are not too precise, it requires good x0 and eps choice. My main question is in lambda conversion.

Upvotes: 2

Views: 121

Answers (1)

bheklilr
bheklilr

Reputation: 54058

If you change your definition of inverseFun such that the (if k == 0 then 1 else k) is instead fromIntegral (if k == 0 then 1 :: Int else k), then you can provide type signatures to all of your functions:

derivation :: (Fractional a)        => (a -> a) -> a -> a
evalA      :: (Fractional a)        => Int -> (a -> a) -> a -> a
inverseFun :: (Fractional a, Ord a) => (a -> a) -> a -> a
f1         :: (Fractional a)        => a -> a

Which certainly helps out.

This is actually important for my solution to your problem, since we need k to be an Int, and you've used it as a Fractional a => a. The fromIntegral fixes that, but it needs to know that it's an Int, so I just added the inline type signature to help the compiler along.

Since your function only depends on the previous single value, you can use our handy friend from Prelude, iterate :: (a -> a) -> a -> [a]. This applies a function over and over again, producing an infinite list of values. We can then index it at any point to get the desired result (this is why having k an Int is important!).

Our function will look like

evalA :: Fractional a => Int -> (a -> a) -> a -> a
evalA k f = iterate go id !! k
    where
        go = ???

Here id is the same as your base case of \x -> x, just shorter and with more optimization rules. It serves as the initial value for generating this list. To implement go, the actual computation, we need it to accept the previous result as its argument:

    where
        go prev = \x -> derivation prev x / derivation f x

But this is considered "poor style" by hlint, and so it is suggested to convert this to the form

    where
        go prev x = derivation prev x / derivation f x

And that's it! I tested it and got the exact same result for your example input. The full code can be viewed here.

Upvotes: 3

Related Questions