[Haskell-beginners] Re: University project - weird problem

[Maciej Piechotka]

On Wed, 2010-04-21 at 20:29 -0300, Renato dos Santos Leal wrote:
> Thank you Stephen!
> 
> Yes, I'm using hugs. My teacher told me to use it and he corrects our
> projects using it, the differece between hugs and GHC, is it large?
> 

Yes and no. I've done basic course of Haskell (not beyond pure
functions) and as I was more familiar with GHC(i) (not mentioning GHC(i)
is a lot faster) I tested using it. Then I changed to hugs and corrected
compilation errors. Usually they were small but still.

> I don't know if I got what you meant with pure functions, but I'll
> keep studying.

http://en.wikipedia.org/wiki/Pure_function

A function that state depends purely on its arguments and which effect
is solely the result.

For example this is pure:

> add :: [(Int, Int)] -> [Int]
> add = map (uncurry (+))

is pure.

But this is not:

> addAndPrint :: [(Int, Int)] -> IO ()
> addAndPrint ((a, b):xs) = do print (a + b)
>                              addAndPrint xs
> addAndPrint []          = return ()

While strict evaluation promotes using impure functions in Haskell pure
functions are often better. Consider:

> add :: [(Int, Int)] -> [Int]
> add = map (uncurry (+))
>
> addAndPrint :: [(Int, Int)] -> IO ()
> addAndPrint xs = mapM print (add xs)

If you have strict evaluation you may think that it will be compiled
into something like:

temportaryList <- add xs
mapM print temportaryList

Creating temportaryList and hence having O(n) space (too bad if it is
infinite list - you will never get the result).

However in Haskell (add xs) is evaluated as needed hence there is no
(significant) delay between adding and printing.


Using the pure functions have significant benefits:
 - They may not change anything. If compiler (not necessary in Haskell -
gcc allows marking function as pure as well) sees some call unnecessary
they may be removed. Consider (in C99)

    for (int i = 0; i < f(); i++)
        doSomething();

    If f is pure it may be compiled into:

    int f_tmp = f(); // I mean real register but anyway. 
    for (int i = 0; i < f_tmp; i++)
        doSomething();

    We save calling f many times (calculating f may be quite costly - 
    10000 number of pi is pure calculation but it may take some time).

    If doSomething is pure we may just not call it (we don't need the
result):

    for (int i = 0; i < f(); i++) {}

    If both are pure compiler just skips loop.

    If you consider haskell example:

    > doSomething :: [Int] -> IO [Int]
    > doSomething (x:xs) = do xs' <- doSomething' xs
    >                         return (x+1):xs'
    > doSomething []     = return []
    >
    > headOfSomething :: [Int] -> IO Int
    > headOfSomething xs = do ys <- doSomething
    >                         return (head ys)

    headOfSomething returns the first element increased by one. However 
    it has to iterate through the list making it in O(n) time.

    > doSomething :: [Int] -> [Int]
    > doSomething (x:xs) = (x+1):doSomething xs
    > doSomething [] = []
    >
    > headOfSomething xs = head (doSomething xs)

   Now we know we can just skip the evaluation of doSomething if we 
   don't need the result. Making it O(1) function.

 - They are nice to test. Pure function depends only on input so there
is no need for setting up environment and checking the environment. What
worst the testing may break the encapsulation as it needs to lookup the
state (to check if it is correct).

 - The order does not matter. If you have map f (map g xs) then it is
sure that the order of f and g does not matter. Compiler may as well
change it into map (f . g) xs (it maye save a little of space and time).

   However if you consider:

   > call f g xs = do ys <- mapM g xs
   >                  mapM f ys

   Then the ordering does matter.


I tried to not use higher order functions & other scary stuff and I'm
sorry if any slipped in.

As you probably noticed Haskell syntax encourages the pure functions. 

While the examples may not make it clear why it is better try to imagine
them 10x more complicated ;)

As a rule of thumb - from syntax point of view if something has IO in
type it is impure. String -> IO (Int) is impure while String -> Int is
pure.

Regards

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/beginners/attachments/20100425/30c1744d/attachment.bin