Haskell: Equation Expander 1+(1+(1+(1+(…))))=∞

Question

Does there exist a equation expander for Haskell?

Something like foldr.com: 1+(1+(1+(1+(…))))=∞

I am new to Haskell I am having trouble understanding why certain equations are more preferable than others. I think it would help if I could see the equations expanded.

For example I found foldr vs foldl difficult to understand at first until I saw them expanded.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z xs = go xs
             where
               go []     = z
               go (y:ys) = y `k` go ys

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

From the definitions I can see that foldr expands like this:

foldr (+) 0 [1..1000000] -->
1 + (foldr (+) 0 [2..1000000]) -->
1 + (2 + (foldr (+) 0 [3..1000000])) -->
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) -->
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) -->

and foldl expands like this:

foldl (+) 0 [1..1000000] -->
foldl (+) (foldl (+) 0 [1]) [2..1000000]) --> 
foldl (+) (foldl (+) (foldl (+) 0 [1])) [3..1000000]) --> 

or from Haskell Wiki on foldr fold foldl':

let z1 =  0 + 1
in foldl (+) z1 [2..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
in foldl (+) z2 [3..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
in foldl (+) z3 [4..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
in foldl (+) z4 [5..1000000] -->

However, I have trouble on larger equations understanding why things work the way they do in Haskell. For example the first sieve function uses 1000 filters while the second sieve function takes only 24 to find the 1001 prime.

primes = sieve [2..]
   where
    sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0] 



primes = 2: 3: sieve (tail primes) [5,7..]
   where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]  
                                    -- or:  filter ((/=0).(`rem`p)) t
                      where (h,~(_:t)) = span (< p*p) xs

Haskell Wiki on Primes

I have spent a good while working out and expanding by hand. I have come to understand how it works. However, an automated tool to expand certain expressions would greatly improve my understanding of Haskell.

In addition I think it could also serve to help questions that seek to optimize Haskell code:

• Optimizing Haskell Code
• Help optimize my haskell code - Calculate the sum of all the primes below two million

Is there a tool to expand Haskell expressions?

Hartwig

I think I remember on the haskell cafe mailing list something that was almost what you want. I think it involved a newtype with a special num instance, but my memory is fuzzy though, I'm not sure I can find it. – Jehiah

Answer 1

David V. Thank you for those links. Repr is definitely worth adding to my tool box. I would like to add some additional libraries that I found useful.

HackageDB : Trace (As of December 12, 2010)

• ghc-events library and program: Library and tool for parsing .eventlog files from GHC
• hood library: Debugging by observing in place
• hpc-strobe library: Hpc-generated strobes for a running Haskell program
• hpc-tracer program: Tracer with AJAX interface

The Hook package seems to be what I am looking for. I will post more samples later today.

Hood

main = runO ex9

ex9 = print $ observe "foldl (+) 0 [1..4]" foldl (+) 0 [1..4]

outputs

10

-- foldl (+) 0 [1..4]
  { \ { \ 0 1  -> 1
      , \ 1 2  -> 3
      , \ 3 3  -> 6
      , \ 6 4  -> 10
      } 0 (1 : 2 : 3 : 4 : []) 
       -> 10
  }

I was unaware of the Hackage library (as I am just getting into Haskell). It reminds me of Perl's CPAN. Thank you for providing those links. This is a great resource.

Hartwig

Answer 2

This is in no way a full reply to your question, but I found a conversation on Haskell-Cafe that have some replies :

http://www.haskell.org/pipermail/haskell-cafe/2010-June/078763.html

That thread links to this package :

http://hackage.haskell.org/package/repr that according to the page "allows you to render overloaded expressions to their textual representation"

The example supplied is :

*Repr> let rd = 1.5 + 2 + (3 + (-4) * (5 - pi / sqrt 6)) :: Repr Double
*Repr> show rd
"fromRational (3 % 2) + 2 + (3 + negate 4 * (5 - pi / sqrt 6))"

Jehiah

Answer 3

This is an answer to an unasked question, think of it as a long comment.

(Please downvote only then below 0, iff you think that it does not fit. I'll remove it then.)

---

As soon as you are a bit more experienced, you might not want to see the way things expand, anymore. You'll want to understand HOW things work, which then supersedes the question WHY it works; you won't gain much just by observing how it expands, anymore.

The way to analyse the code is much simpler than you might think: Just label every parameter/variable either as "evaluated" or "unevaluated" or "to-be-evaluated", depending on the progression of their causal connections.

Two examples:

---

1.) fibs

The list of all Fibonacci Numbers is

fibs :: (Num a) => [a]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The first two elements are already evaluated; so, label the 3rd element (which has value 2) as to-be-evaluated and all remaining as unevaluated. The 3rd element will then be the (+)-combination of the first elements of fibs and tail fibs, which will be the 1st and 2nd element of fibs, which are already labelled as evaluated. This works with the n-th element to-be-evaluated and the (n-2)-nd and (n-1)-st already evaluated elements respectively.

You can visualize this in different ways, i.e.:

  fibs!!(i+0)
+ fibs!!(i+1)
= fibs!!(i+2)

            (fibs)
zipWith(+)  (tail fibs)
        =   (drop 2 fibs)

          1 : 1 : 2 : 3 ...
     (1 :)1 : 2 : 3 : 5 ...
 (1 : 1 :)2 : 3 : 5 : 8 ...

---

2.) Your example "sieve (p:ps) xs"

primes = 2: 3: sieve (tail primes) [5,7..]
   where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]  
                                    -- or:  filter ((/=0).(`rem`p)) t
                      where (h,~(_:t)) = span (< p*p) xs

In "sieve (p:ps) xs",

• p is evaluated,
• ps is unevaluated, and
• xs is an evaluated infinite partialy-sieved list (not containing p but containing p²), which you can guess reading the recursion and/or recognizing that the values of h need to be prime.

Sieve should return the list of primes after p, so at least the next prime is to-be-evaluated.

• The next prime will be in the list h, which is the list of all (already sieved) numbers k where p < k < p²; h contains only primes because xs does neither contain p nor any number divisible by any prime below p.
• t contains all numbers of xs above p². t should be evaluated lazy instead of as soon as possible, because there might not even be the need to evaluate all elements in h. (Only the first element of h is to-be-evaluated.)

The rest of the function definition is the recursion, where the next xs is t with all n*p sieved out.

---

In the case of foldr, an analysis will show that the "go" is only defined to speed up the runtime, not the readability. Here is an alternative definition, that is easier to analyse:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr (.:) e (x:xs) = x .: (foldr (.:) e xs)
foldr (.:) e []     = e

I've described its functionality here (without analysis).

To train this type of analysing, you might want to read the sources of some standard libraries; i.e. scanl, scanr, unfoldr in the source of Data.List.

Scruffy

What is does the function (.:) mean? – Hartwig

(.:) is a parameter of type (a->b->b). If you replace (.:) with f, then you would have to replace .: with `f`. – Scruffy