News for hackers. Stuff that matters.
Re:Programming Without Variables by crntaylor on Friday September 13, 2013 @03:17AM (#6379121)
Nice article. I don't really understand the final point, though. Here's a simple implementation of the collatz function that returns the entire list iterated through, using a simple data structure, and that is O(I) in the number of iterations I

    collatz_vec :: Int -> [Int]
    collatz_vec = reverse . go []
      where
	go acc 1 = acc
	go acc n = go (n:acc) (if even n
		then div n 2
		else 3 * n + 1)
You simply push new values to the front of the list rather than the end, and then reverse the list all in one go at the end. Sure, you could use a fancier data type like an IntMap, but why bother when you already have linear complexity with a simple one?

Edit: In fact, here's an even simpler solution that doesn't need to reverse the final result

    collatz_vec :: Int -> [Int]
    collatz_vec = takeWhile (/= 1) . iterate step
      where
        step 1 = 1
        step n = if even n then div n 2 else 3 * n + 1
It's not tail recursive (because it uses `iterate`) but it's lazy -- so if the elements of the list are consumed as they are created, the whole computation can be done in constant space as well as being fast.
Re:Programming Without Variables by secretguy on Friday September 13, 2013 @05:43AM (#6379431)
Or perhaps like this if you do not want to use `reverse` and want it to be tail recursive:

    collatz :: Int -> [Int]
    collatz x = go id x []
      where
        go :: ([Int] -> [Int]) -> Int -> [Int] -> [Int]
        go f 1 = f . (1:) 
        go f n = 
          if even n
            then go (f . (n:)) (n `div` 2)
            else go (f . (n:)) (3 * n + 1)
Re:Programming Without Variables by masklinn on Friday September 13, 2013 @05:58AM (#6379458)
Why would you want to not use reverse? (tail-recursion is orthogonal, and I understand not really useful in haskell unless you force strict evaluation though I may be wrong)
Re:Programming Without Variables by zeckalpha on Friday September 13, 2013 @08:49AM (#6380084)
It increases the constant time, as reverse is O(n).
Re:Programming Without Variables by wging on Friday September 13, 2013 @03:34AM (#6379166)
Part of the point seems to be to explain the efficient implementation of such an approach. (How would you write GHC if you didn't have it available...?) Try to translate your code into C++...
Re:Programming Without Variables by crntaylor on Friday September 13, 2013 @03:37AM (#6379170)
I don't write C++, but if it has linked lists then at least the first one should be trivial. The second one would probably involve function pointers.

Maybe his point was that you need to use a linked list rather than an array to get an efficient solution? Coming from a Scheme/ML/Haskell background I tend to view linked lists as much simpler than arrays!

Re:Programming Without Variables by jfarmer on Friday September 13, 2013 @03:54AM (#6379207)
Consider the author concluded with

> In effect, the whole idea of an array is built on being able to change part of it, and if we intend to avoid changing memory once we have put values into it, we need another kind of data structure entirely. Next week, we'll look at what such a data structure might be.

I'm assuming that a linked list is precisely the data structure he'll introduce next week. ;)