Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reverse iteration #76

Closed
benny-medflyt opened this issue Dec 16, 2018 · 10 comments
Closed

Reverse iteration #76

benny-medflyt opened this issue Dec 16, 2018 · 10 comments

Comments

@benny-medflyt
Copy link

I can't find a way to loop over a List backwards. The only way seems to be to use reverse, but this is very inefficient for large lists.

There is reduceRight/foldr, but those don't allow for early termination.

I think we need a function

function reverseIterator<A>(l: List<A>): Iterator<A>;

(Similar to C++ rbegin/rend)

@benny-medflyt
Copy link
Author

Just to give an example use case: Let's say we need to find the first number in a List that is greater that 10, but searching from the back to the front. Here is how we could write it using reverse:

import * as L from "list";

function firstOverTenFromBack(list: List<number>): number | null {
    for (const num of list.reverse()) {
        if (num > 10) {
            return num;
        }
    }
    return null;
}

const myList = L.from([1, 5, 20, 16, 4, 5, 11, 2, 5]);
console.log(firstOverTenFromBack(myList)); // 11

But this is very inefficient when the List is large.

@paldepind
Copy link
Member

This is a great idea and relates slightly to #75.

What are you actually most interested in a reduce an reduceRight that supports early termination or an iterator that iterates backwards?

I'd like to add both but I'd also like to work on the most "important" one first.

@benny-medflyt
Copy link
Author

I personally would be interested in a reverse iterator, so I can use it with regular for loops. My personal style is to try to use for loops when possible, rather than a functional style, in order to keep the code familiar for other javascript programmers.

@levino
Copy link

levino commented Dec 17, 2018

My personal style is to try to use for loops when possible, rather than a functional style, in order to keep the code familiar for other javascript programmers.

Then you should not use list. It is for functional programming. Just use arrays.

Also reversing the list should be O(1) if it is a double linked list, so I would say that is very efficient.

@levino
Copy link

levino commented Dec 17, 2018

Maybe I am wrong. Looks like the underlying data structure is a JS array...

@paldepind
Copy link
Member

Looks like the underlying data structure is a JS array...

The underlying data structure is a relaxed radix balanced tree. Since the data structure is symmetric it actually is possible to reverse it in O(1). But I've been hesitant to do so as it adds extra complexity for all the other operators.

My personal style is to try to use for loops when possible, rather than a functional style, in order to keep the code familiar for other javascript programmers.

I will be happy to add a backwards iterator. But, the alternatives to for-of loops are typically reduce and map which I think any JavaScript developer should be familiar with.

@paldepind
Copy link
Member

@benny-medflyt

What do you think about the name backwards as the function that returns an iterable that iterates in reverse order?

for (const element of backwards(myList)) {
  ...
}

@benny-medflyt
Copy link
Author

that backwards function looks perfect!

@paldepind
Copy link
Member

@benny-medflyt I've finally gotten around to add the backwards function 😄 I'm going to add a few other requested features and then I'll publish a release to npm that includes backwards.

@paldepind
Copy link
Member

This is now release as part of 2.0.17.

Thanks a lot for the feature request @benny-medflyt and for your patience 😉

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants