Zip Function Solution: Haskell, Elixir, JavaScript, Python, Vlang | Hacker News Reader

Zip Function Solution: Haskell, Elixir, JavaScript, Python, Vlang

kevin-da-silva.medium.com

44 pointsTozen65 comments

It's a good learning exercise.

Of course, don't use your own hand crafted version in Python, since one is provided with the language and it is better than the one you will likely come up with.

Still, it's interesting because it's simple. So starting from the intro of this article, if you want to go further, try to do the following to match up __builtins__.zip:

- make it lazy (yield would work)

- make it work with any iterable (iter() + StopIteration would work)

- put some type int and a docstring (so that help() gives you informations)

- accept any number of iterables (variadic parameters would work)

- make a second version that accepts a fill value (like itertools.zip_longest)

This will sharpen your python skills, and also will make you appreciate even better how much you get for free with the stdlib (not to mention __builtins__.zip is in C, so it's fast).

It's worth noting that `map` is variadic and acts as an nary `zipWith`. I didn't realize that for a while.

    >>> from operator import `add`
    >>> list(map(add, range(5), range(10, 15)))
    [10, 12, 14, 16, 18]
    >>> add3 = lambda x,y,z: x+y+z
    >>> list(map(add3, range(5), range(10, 15), range(100, 105)))
    [110, 113, 116, 119, 122]

> will make you appreciate even better how much you get for free

This is unironically the reason I come back to Python again and again. The language itself is not my favorite: it 'should' be different. But my productivity with it is frankly unmatched.

The "zip" example is an excellent case study. The actual "zip" is by default lazy, it accepts arbitrary iterators, etc. It's the "correct" solution, unlike the one presented in the article, and I have it at my fingertips, in the standard library.

> This is unironically the reason

Can I ask an off topic question? Where did this sudden popular use of “unironically” come from? I don’t get it. Why would it be ironic?

It reminds me of the sudden rise of “literally” a decade or so ago.

"Unironically" here means "seriously", "literally", "actually", etc. It's basically a marker that the speaker is speaking straightly and plainly, without trying to make a joke.

Yes, it's not really antonymous to "ironically" (in the narrower sense of this word) in this context.

I think it's fairly literal, there's a whole brand of humor around pretending to like things that you actually like. "I like C because of all the undefined behavior".

But this is also how word meanings shift over time. Someone will see someone else using that word and not know what it means, but then start using it, etc.

In reality most of these are really simple, the big question is how to handle end of iteration across iterators e.g. given zip(a, b) where a is shorter than b, on the last iteration will b get updated or not?

In Python an iterator is simply an object that implements the __next__ method, and raises StopIteration to signal the end of the iteration.

It's not hard to implement just about any protocol on top of that abstraction, e.g. you have itertools.zip_longest()

I know what an iterator is. I think you missed the point.

Would you like to explain that further?

Progressing an iterator is a side-effect (a mutation).

Depending how the last iteration is handled, zip(a, b) and zip(b, a) with iterators of different sizes can have different behaviours: if a is shorter than b, a naïve implementation would update b in the zip(b, a) case, but not in the zip(a, b) case.

There is no unique solution to that problem since sometime you want consumption, and sometimes not, for one or more of the parameters.

__builtins__.zip chose to consume iterators in the order they are passed as a parameter, and therefor end up with an assymetric consumption.

That's why itertools.tee exists, so that we can chose case by case.

That reminds me of a lovely paper "How to Add Laziness to a Strict Language Without Even Being Odd" by Wadler and MacQuenn. They use "map" as their running example, but the problem is basically the same.

zip is generally implemented as a functional concept, where the iterators take values from the backing iterable structure "by const &". You can implement a custom mutating zip operation on top of the iterator protocol.

I believe masklinn is talking about whether `zip` consumes an extra element from the longer iterator on the last iteration, when the shorter iterator raises StopIteration. And the behavior might vary depending on the order of the arguments.

    def a():
      yield "a1"

    def b():
      yield "b1"
      yield "b2"

    x,y = a(),b()
    zip(x,y) # => [("a1","b1")]
    next(x) # => raise StopIteration
    next(y) # => "b2"

    x,y = a(),b()
    zip(y,x) # => [("b1","a1")]
    next(x) # => raise StopIteration
    next(y) # => raise StopIteration

This is the problem with python's conflation of iterable and iterator, and maybe why so many programmers don't understand the difference when they pick up Java.

> This is the problem with python's conflation of iterable and iterator

It really is not. It’s just a natural outcome of imperative langages. If operations can have side-effects, then combinator behaviour will affect those side-effects.

You could do the same with iterables with side-effecting iterations.

It’s also perfectly logical to be able to iterate an iterator.

Common Lisp version, works with an arbitrary number of lists and automatically trims the result to the length of the shortest list.

    (defun zip (&rest lists)
      (apply #'mapcar #'list lists))

Example:

    CL-USER> (zip '(1 2 3) '(4 5 6 7 8) '(a b c d))
    ((1 4 A) (2 5 B) (3 6 C))

Limited by the implementation specific max number of arguments.

A simpler (IMHO) Python version, plus lazy and working on any iterable. Also, it's quite easy to adapt it to work on any number of iterables.

    def myzip(x, y):
        x, y = iter(x), iter(y)
        try:
            while True:
                yield next(x), next(y)
        except StopIteration:
            return

I was looking for a way to implement this more pythonically. And this looks great. But it made me think that if x and y are of different lengths, the last iteration might consume an element out of the longer iterator.

So I tried it with the builtin `zip(a,b)`, and indeed, if a is shorter, `zip(a,b)` consumes the same number of elements from both a and b. But if a is longer, then `zip(a,b)` consumes one extra element from a. I don't know if this behavior is well defined, that is whether I can rely on this, or the order of evaluation of the arguments of a function is up to the interpreter/compiler, and may change.

masklinn wrote a comment in another thread about this that i didn't understand until I saw your implementation.

    def myzip(*seqs):
        next_yield = [None] * len(seqs)
        its = [iter(seq) for seq in seqs]
        should_go = True

        while should_go:
            for index, it in enumerate(its):
                try:
                    next_yield[index] = next(it)
                except StopIteration:
                    should_go = False

            if should_go:
                yield tuple(next_yield)

It consumes exactly the same number of elements from all sequences, unless a non-StopIteration exception occurs during the iteration.

I‘m not good in JavaScript, but reading the code, I wonder if this implementation doesn’t have an issue with truthiness in the second array. For example if you zip([true,true],[false,false]).

The minimum length approach seams to be the better one. (Without having it run anywhere.)

That was my quick reaction as well... I think it would need something like the python example below, where you first check the lengths of the two arrays/lists, and then iterate over that, and not directly over the length of the first list.

    iter_limit = Math.min(ls1.length, ls2.length);
    for(let i = 0; i < iter_limit; i++)...

  function zip(arr_a, arr_b) {
    const len = arr_a.length < arr_b.length ? arr_a.length : arr_b.length;

    return arr_a.slice(0, len).map((el, idx) => [el, arr_b[idx]]);
  }

Yes, the JavaScript implementation doesn't works if the second array contains 'false', 'null', 'undefined', '0' or 'NaN'.

Here is my implementation of the 'zip' function in modern JavaScript. It is similar to the Vlang version, but it is generic over the number of arrays :

  const zip = (...arrays) => {
    const length = Math.min(...arrays.map((array) => array.length));
    return Array.from({ length }, (_, i) => arrays.map((array) => array[i]));
  };

Generally in Python it's much better to use list comprehensions when possible, it offers significant speedups usually:

  def zip(ls1, ls2):
      return [(ls1[i], ls2[i]) for i in range(min(len(ls1), len(ls2)))]

And indeed you could even use a generator instead:

  def zip(ls1, ls2):
      return ((ls1[i], ls2[i]) for i in range(min(len(ls1), len(ls2))))

The inclusion of Vlang is interesting. I remember that it was created together with Volt, a multi-service messenger app that never delivered. Is the language any good, and are there any advantages over more established esoteric systems languages like D, Nim, or Zig?

From a pure language perspective, not taking into account infrastructure and implementation, Vlang is currently my favorite language. It has pretty much the syntax and semantics I want in a statically compiled, strongly typed language. However, there are still too many features of the current implementations that are in reality not yet implemented or too experimental. It's still not ready for production and larger projects.

I'd say the languages you mention are substitutes according to the following mapping:

    C++    => D
    Python => Nim
    C      => Zig
    Go     => V

V promised a lot of stuff as ready but has undelivered most of them and people lost trust. If V was truthful like Zig, it would be able to create a foundation. Also a programming language will never be able to substitute another one if it is not able to call its vast number of libraries.

I agree, the table refers to the intention of the language developers and how the languages feel, it's not about real substitution. For example, D was explicitly designed as a better version of C++ and also allows you to use C++ libraries directly, and Zig is explicitly intended as a modern substitute for C.

As for V, it delivers quite well for a language at such an early stage and has a growing community. IMHO, it's a great language.

Still would not use V myself, its the prime example of overmarketing of impossible features, silencing of critics online etc

Since you are comparing Zig with V:

> V promised a lot of stuff as ready but has undelivered most of them

This is wrong. V has an online playground, a package manager, hot code reloading and a REPL whereas Zig doesn't even though Zig is twice as old.

> If V was truthful like Zig, it would be able to create a foundation

Raising money doesn't lead to adoption, though. By this logic, C isn't truthful either since it doesn't have a foundation.

> Also a programming language will never be able to substitute another one if it is not able to call its vast number of libraries

How is this relevant? Both Zig and V can call C code and leverage C's ecosystem of libraries.

This comment started a hellish flamewar. Please don't start programming language flamewars on HN. Last thing we need here.

https://news.ycombinator.com/newsguidelines.html

D and Nim are great mature languages. If you think they're suitable for the domain you're working on and reach out for either of them, you're not gonna go wrong. They have large communities and you'll easily find answers to your questions.

I wouldn't call Zig established, though. Zig's compiler still crashes on valid code and compared to V it still doesn't have an online playground, a package manager, hot code reloading, a REPL, etc. even though it's twice as old.

V's syntax is similar to Go. However under the hood V differs from Go. For example:

- V has compile-time memory management similar to the Lobster programming language.

- V has zero-cost interoperability with C.

Check it out and decide for yourself. If you already know Go, you can learn V in an afternoon.

Nim is very fast but also very expressive. Think of a compiled Python, but with Rust-like safety.

In TCL, zip functionality is built into the foreach loop.

     foreach x $list1 y $list2 {
         lappend result [Myfunc $x $y]
     }

To directly return a list of outputs without having to append to a list, TCL also provides lmap which works the same way:

     lmap x $list1 y $list2 {Myfunc $x $y}

But wait there's more! Foreach and lmap also support taking more than one element from the list each time:

     lmap {x y} $list1 {Myfunc $x $y}

It's gauche to flaunt the power of the gods among mortals.

For Python, I’d prefer a generator over appending. Less imperative style-wise and faster too I think.

Also working with iterables rather than requiring sequence.

Aka all the things the builtin does (well it also supports zipping an arbitrary number of iterables).

Indeed. FWIW I meant ‘comprehension, rather than ‘generator’, but hey, both would work

FP is nice, but logic programming also has its niceties.

  (define (zipo a b z)
    (conde ((nullo a) (nullo z))
           ((nullo b) (pairo a) (nullo z))
           ((fresh (ahead atail bhead btail ztail)
              (conso ahead atail a)
              (conso bhead btail b)
              (conso (list ahead bhead) ztail z)
              (zipo atail btail ztail)))))

  (run* (q) (zipo '(1 2 3) '(a b c) q))
  => (((1 a) (2 b) (3 c)))
  (run* (q) (zipo '(1 2 3) q '((1 a) (2 b) (3 c)))
  => ((a b c . _.0))

Interestingly, the post says "JavaScript [...] has tail call issues", but at least the Elixir algorithm is not tail recursive and will blow up with inputs that are too big.

Make it simple, THEN make it fast/efficient.

Here's a tail-recursive function. To be honest I would have started writing this version first, the acc pattern is ubiquitous. Sorry for the mistakes, I'm on mobile:

    def zip(a, b) do
      zip(a, b, [])
    end

    def zip([], _, acc), do: acc

    def zip(_, [], acc), do: acc

    def zip([a | a_rest], [b | b_rest], acc) do
      zip(a_rest, b_rest, [{a,b}|acc])
    end

Also, there's Enum.zip/2 in the standard library, with the bonus that it works with any Enumerable type (lists, maps, lazy streams, etc,)

Sure, but if we want to highlight other languages' lack of tail call support, maybe we should showcase that support in those languages that do support it. :)

The JavaScript one is incorrect. It should use the length of the 2nd list rather than stop at the first falsy value in it.

That's where I stopped reading. Even going in, I wondered doesn't each of these languages already have a function in stdlib or a de-facto package with it?

My solution for Javascript:

  function zip(arr_a, arr_b) {
    const len = arr_a.length < arr_b.length ? arr_a.length : arr_b.length;

    return arr_a.slice(0, len).map((el, idx) => [el, arr_b[idx]]);
  }

zip is useful to have as a library function in a Lisp dialect in spite of being easily able to compose it with mapcar and list.

It comes up fairly often in macros. E.g. you have gens, a list of gensyms, and exprs, a list of expressions, and body, a list of forms that refer to the gensyms:

  `(let ,(zip gens exprs) ,@body)

In JavaScript:

  let zip = (as,bs) => as.slice(0, Math.min(as.length,bs.length)).map((a,i) => [a,bs[i]]);

  {(,')over min[count each x]#'x}

k4:

  {,'/(&/#:'x)#'x}

Reply on news.ycombinator.com