Proposed new syntax

[Steve D'Aprano]

On Tue, 15 Aug 2017 01:40 am, Chris Angelico wrote:

[...]
>> A Haskell list comprehension is not a loop at all.
> 
> What if you don't take the first four, but instead take just the tenth
> element? Will the preceding elements be calculated too, or do you have
> a sparse list? 

Both. Or neither.

The preceding elements aren't *calculated*, but they are *allocated* ready for
when you need them:

Prelude> let squares = [ x ** 2 | x <- [1 ..] ] :: [Float]
Prelude> squares !! 10
121.0
Prelude> :print squares
squares = (_t2::Float) : (_t3::Float) : (_t4::Float) :
          (_t5::Float) : (_t6::Float) : (_t7::Float) : (_t8::Float) :
          (_t9::Float) : (_t10::Float) : (_t11::Float) : 121.0 :
          (_t12::[Float])


Haskell lists are single-pointer linked lists.

https://wiki.haskell.org/How_to_work_on_lists

My understanding of it is that it will be implemented something like a linked
list of thunks, followed by the evaluated element, followed by an infinite
generator. In Python terms:

(lambda x=1: x**2, 
    (lambda x=2: x**2, 
        (lambda x=3: x**2,
        ... # for brevity
            (lambda x=10: x**2,
                (121.0, 
                    ((x**2 for x in itertools.count(12)), None)
                )
            )
        ...
        )
    )
)

or something more-or-less equivalent.

It's quite clever, actually, in that it gives *pseudo* random-access with lazy
evaluation. You can evaluate the Nth element without evaluating the earlier
ones. But you can't do so without *storing* the previous ones, they have to be
allocated, with only the actual evaluation being delayed.

So its both less powerful and more powerful than Python's (x)range. Less
powerful as:

- there's no random access (you have to walk the linked list to get 
  to the Nth element, touching each element in turn);

- and you cannot access the Nth element without storing the previous
  N-1 elements.

But more powerful in that, like a generator expression, it can take arbitrary
expressions.


Here's a more interesting example:

Prelude> let squares = [ x ** 2 | x <- [1 ..] ] :: [Float]
Prelude> let values = [a + 1 | a <- squares ] :: [Float]
Prelude> values !! 4
26.0
Prelude> :print values
values = (_t13::Float) : (_t14::Float) : (_t15::Float) :
         (_t16::Float) : 26.0 : (_t17::[Float])
Prelude> :print squares
squares = (_t18::Float) : (_t19::Float) : (_t20::Float) :
          (_t21::Float) : 25.0 : (_t22::[Float])

So its lazy evaluation all the way down.

I think the closest analogy in Python terms would be a generator expression with
a cache. That's not *quite* the same, because Python is eagerly evaluated and
Haskell is lazily evaluated, but the critical fact (which Ian seems to have
completely missed) is that while evaluation can be delayed, touching each
element *in order* from start to end cannot be. You cannot jump to an arbitrary
index in Haskell.

But one thing is sure: even if evaluation is delayed, before you can access
element N, you have to access element N-1. Whether it is implemented via
recursion, a while-loop, or an actual for-loop, it is still logically
equivalent to a for-loop through the elements.


In Haskell, you cannot get the last N elements of a list without allocating
memory for the previous ones. Here's a Stackoverflow post about it:

https://stackoverflow.com/questions/17252851/how-do-i-take-the-last-n-elements-of-a-list


-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.