4

This is an example of my current code:

DataSet = [1,2,3,4,5,6,7,8,9].

Sequence = [3,4,5,6].

ReducedDataSet = lists:foldl( fun(SeqNumber, Output) ->
                                 Row = lists:nth(SeqNumber, DataSet),
                                 [Row|Output]
                              end,
                              [],
                              Sequence
                             ).

ReducedDataSet ends up as [6,5,4,3] and if I change it to lists:foldr, ReducedDataSet would be [3,4,5,6].

I didn't expect this as when absorbed left to right, the 3rd value is 3 and should proceed to 6, but when absorbed right to left, the 3rd value would be 7, and proceed to 4.

Does this mean there's a hidden row number on my list, and foldl and foldr only differ in the sort order of the final list?

Philbo
  • 143
  • 4

2 Answers2

4

I think this is a more general fold question.

In general, fold performs the following: (new_element, acc) -> new_acc

If the operation new_element ° acc is commutative (e.g. the sum), foldl and foldr are the same.

If the operation is "append" there is a difference between appending the element to the left or to the right.

[3] ° 4 -> [3, 4] VS 4 ° [3] -> [4, 3]

I never remember which is foldl and foldr but I think left/right refers to the position of the accumulator ([3] ° 4 is foldl with this definition)

pazqo
  • 477
  • 3
  • 9
  • 2
    To be honest, with your answer I've realised I'm focusing on the wrong thing here. As you say foldl and foldr are just determining the position of elements added to an accumulated new list, its lists:nth that is using the static original DataSet and determining each position. To lists:nth, the 3rd element is always in the 3rd position, regardless of what I do with that element once I've got it. – Philbo Sep 12 '17 at 08:55
3

TL;DR

No, there is no hidden index or "row number" in an Erlang list.

Discussion

It may be helpful to explore the nature of list operations a bit more in the context of functional lists of the "lists are a bunch of conses" variety.

I wrote an explanation of folds a while back that might be useful to you: Explanation of lists:fold function

Keep in mind that functional lists only have pointers that go one-way. That is, they are singly linked lists. There is no concept of a "rownum" or "index" as it would be in a C style array. Each call to lists:nth/2 is actually traversing the list to the nth element before returning that element.

We could write lists:nth/2 like this if we want a version that crashes on bad input (and, looking it up, it turns out that it is written almost exactly like this):

nth(1, [Element | _]) ->
    Element;
nth(N, [_ | Rest]) when N > 1 ->
    lists:nth(N - 1, Rest).

(As a side note, consider not inlining funs that require you to write multi-line definitions as function arguments...)

zxq9
  • 13,020
  • 1
  • 43
  • 60
  • Think this answers my question as best I asked it. The other answer is a nice quick reminder on fold, but as I myself realised, the answer was to remember it was lists:nth that was determining position in the list. – Philbo Sep 12 '17 at 14:49
  • I'm also not a fan of how we're currently writing multi-line functions - how I wrote it above just reflects how we're currently doing it. Going to send your link onwards to my senior, see if it makes a more convincing argument than I've managed to. – Philbo Sep 12 '17 at 14:51
  • @Philbo Not everyone agrees with me that disintegrating things is a good idea. I have found that very often well named functions are easier to deal with (and find reuse elsewhere) than inlined funs, and in almost all cases assigning a meaningful label to an otherwise anonymous function within a larger function is almost always a readability win. Those readability wins *really* add up over time, though, especially when you go back to rework some old code. As for general style, I wrote an example project for that purpose based on available graybeard advice: https://github.com/zxq9/zuuid – zxq9 Sep 13 '17 at 02:32