These are chat archives for evhub/coconut

17th
Aug 2016
Chuck Daniels
@chuckwondo
Aug 17 2016 20:50

@evhub I’m having some trouble with pattern-matching functions dealing with sequences/iterables/generators in terms of terminating recursion. As a way to wrap my head around how Coconut is dealing with things, I’ve written the following sieve:

def sieve([]) = []

@addpattern(sieve)
def sieve([head] :: tail) = [head] :: sieve(n for n in tail if n % head)

primes = sieve([2, 3, 4, 5])
print(list(primes))

Unfortunately, I get a match error from list(primes). Similarly, when I replace the last line with repeated calls of print(next(primes)), I see the 3 primes in the list printed, but then get the same match error when attempting to call next beyond the end of the generator.

My question is, how do I properly pattern match in order to properly bump into StopIteration instead, so that I can make a successful call to list(primes) to yield the list of primes without hitting a match error?

I can see why the empty generator doesn’t match the empty list pattern. The generated code is matching against a Sequence, not an Iterable, in the first function pattern. In the second function pattern, it’s correctly looking for an Iterable, but when the iterable is exhausted, the match fails because there is no head.

I’m stumped as to how to properly match the terminal recursion.

Evan Hubinger
@evhub
Aug 17 2016 22:53
@chuckwondo The proper way to match an empty iterator is to use the syntax for the empty lazy list, (||). However, even with that change, your code still won't work. Paradoxically, you actually have to match the empty iterator last, not first. That's because Python iterators aren't real lazy lists in that once they're exhausted, you can't go back and see what used to be in them. Thus, if you check for the empty iterator first, Coconut will fully exhaust the iterator, throw it away, and leave nothing left to match your [head] :: tail pattern. The correct, working version of the above is:
def sieve((||)) = [] # or (||), if you always want to return an iterator not a list

@prepattern(sieve)
def sieve([head] :: tail) = [head] :: sieve(n for n in tail if n % head)

primes = sieve([2, 3, 4, 5])
print(list(primes))
Evan Hubinger
@evhub
Aug 17 2016 23:09
I just opened #148 to better document the above use case.