Repeat

Implementing repeat in Haskell can be quite straightforward, but if not careful, you can end up with memory inefficient code. Trying to do the same in STG makes the inefficiency quite obvious, with the efficient implementation almost being more natural to write. Lets take a look.

Naiive

Simulator link

Here, the spine of the repeated list is generated by function calls, which creates new objects on the heap.

repeat x = x : repeat x

repeat = FUN(x -> let t = THUNK(repeat_naiive x)
					  l = CON(Cons x t)
				  in l)

Efficient

Simulator link

But we don’t really need to generate the spine. Since the value of the repeated element is always the same, the spine can stay the same as well.

repeat x = let r = x : r in r

repeat = FUN(x -> letrec l = CON(Cons x l)
				  in l)