Hacker News new | past | comments | ask | show | jobs | submit login

That’s frankly not a linked list.



Haskell has a duality between flow control and data structures as a result of its laziness. It is a perfectly valid point of view to look at such a thing as a control structure, rather than a data structure.

Technically, if you want to really understand how the "IO monad" does its thing, this is actually how it works. Technically your program declares a probably-infinite data structure that contains all possible paths your code could take, e.g., if you have a "if user input is negative then do X else do Y", what you really have is a data structure representing the if-then clause. What keeps the infinite data structure from being manifested in RAM is that the whole thing is resolved lazily, so only one branch will be actually evaluated. That's why the "IO monad" is actually pure; it simply "purely" creates a huge data structure that is resolved by an interpreter later. In the theoriest of theories, an IO value in Haskell really doesn't execute anything either and the whole language is pure... it is only the interpretation of the IO value that finally interfaces with the real world.

It isn't always the most helpful perspective and you can become an expert Haskell programmer without ever looking at your program this way, but technically, under the theory hood, that's what's happening.


Haskell is lazy, all data structures work this way unless specifically annotated otherwise. Within standard haskell 2010 it is hard to declare a linked list that doesn't work this way.

It is also worth noting that haskell has library specified fusion rules so the closure isn't even allocated most of the time. So

    sum (take 10 [0..])
compiles into an allocation free loop. I will give you that this isn't a linked list anymore, though.


In Haskell lazy values are just thunks. So a Lisp-style cons can have a tail that's just a thunk, and when you need to coerce it to a non-thunk value, it just happens and presto, you have the next cons. That's a list! A lazy list.


Why not?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: