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)

4
  • 5
    The right ellipsis probably represents the extra parens ))) that would be inserted. Don't overthink this.
    – amon
    Oct 9, 2020 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. Oct 9, 2020 at 10:18
  • @BartvanIngenSchenau: Not without the image, it isn't. Questions really should be understandable without images. Oct 9, 2020 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, 2020 at 10:32

1 Answer 1

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).

1
  • 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, 2020 at 15:23

Your Answer

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

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