1

I've encountered the infomral definition of foldr in a couple of books.

I've attached an image from Bird and Wadler's "Introduction to Functional Programming" (1988), but I've seen the same informal definition in Hutton's "Programming in Haskell" (2nd ed).

In the image attached I'm referring to the 1st and 3rd lines, and what puzzles me is why is there an ellipsis (the 3 dots) to the right of (f x_n a) in the 1st line, or to the right of (x_n # a) in the 3rd line (I'm using '#' in place of the operator that has a circle with a '+' in it).

If we look at the last 4 lines of the image attached we can see that after the operator is applied to the initial value 'a' then all there is to the right are the terminating closing parentheses.

Many thanks, Sarel

P.S. This is a a question about functional programming, which is why I'm posting it in "Software Engineering Stack Exchange" rather than in "Math Exchange". However, I was in need of some math formatting (such as the circle with a '+' in it, or 'x' with a subscript 'n') - is there a way to do that in "Software Engineering Stack Exchange"? Should I have posted it elsewhere?

Informal definition of foldr in Bird and Wadler (1988)

  • 5
    The right ellipsis probably represents the extra parens ))) that would be inserted. Don't overthink this. – amon Oct 9 at 8:05
  • 1
    To answer your PS: Proper math formatting is too rarely needed here that MathJax is not supported on SE.se. Subscripts can be achieved with the HTML <sub> tag and for other symbols you would need to resort to inserting Unicode characters. But your post is perfectly understandable without the proper math formatting. – Bart van Ingen Schenau Oct 9 at 10:18
  • @BartvanIngenSchenau: Not without the image, it isn't. Questions really should be understandable without images. – Jörg W Mittag Oct 9 at 10:20
  • @JörgWMittag: Considering that the question was regarding something written in a textbook (and the image was taken from the textbook), how would you recommend my doing this better next time? I imagine it would be a hassle to replicate the expression I had a problem with in text form (as it was more mathematically oriented, and MathJax is not supported on SE.se, as Bart van Ingen Schenau kindly pointed out). I'm actually interested if there's a (relatively) hassle-free way of asking my question in text form, without relying on the image from clarity. – Sarel Oct 10 at 10:32
5

I agree with @Amon in his comment.

The right-hand ellipsis represents the additional closing brackets that would be present for additional items.

The definition of FoldR is straightforward - it's simply the interposition of a dyadic operator between each element, but with evaluation beginning at the right (i.e. the tail) of the array (unlike FoldL which begins at the left, or the head).

| improve this answer | |
  • Thank you all for your quick and friendly answers. After your pointing it out it suddenly seems obvious that the ellipsis represents the unspecified number of parentheses. It was bugging me, and it feels better understanding it now. – Sarel Oct 9 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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