Why do you say so? It's equivalent to iterating indexes from 0 to N-1 of two (or more) lists with N elements and providing syntax sugar for those lists' elements at that index. This is O(N).

Right, it's not an ordinary list comprehension. It's a parallel list comprehension though:

  zip as bs = [(a,b) | a <- as | b <- bs]

https://downloads.haskell.org/ghc/latest/docs/users_guide/ex...