flatten an array

flatten.coffee

# Let's set up a quick and dirty test framework

# a helper to define the tests
expect = (expected, input) ->
  [expected, input]

# an array equivalence test
areSameArrays = (left, right) ->
  return no unless left.length is right.length
  for i of left
    return no unless left[i] is right[i]
  yes

# run a single test
runTest = (test, fn) ->
  result = fn test[1]
  if areSameArrays test[0], result
    yes
  else
    console.log "Expected:", test[0], "saw", result, "on input", test[1]
    no

# run the suite of tests
runTests = (tests, fn) ->
  pass = 0
  fail = 0
  for test in tests
    if runTest test, fn
      pass += 1
    else
      fail += 1
  console.log "#{tests.length} tests run, #{pass} passed, #{fail} failed"

# the various tests to run
tests = [
  # trivial cases
  expect [], []
  expect [1],  [1]
  expect [1], [[[[1]]]]
  expect [1, 2], [1, 2]

  # starting to get interesting
  expect [1, 2, 3], [1, [2, [3]]]
  expect [1, 2, 3, 4], [[1, []], [2], [[], [3, [4]]]]
  expect [1, 2, 3], [[[1], 2], 3]

  # the given examples
  expect [1, 2, 3, 4], [[1,2,[3]],4]
]

# the implementation

# we'll use a husk-and-kernel method to force tail recursion
flattenKernel = (previous, remaining) ->
  return previous if remaining.length is 0
  here = if Array.isArray remaining[0]
    # depth-first recursive call
    flattenKernel previous, remaining[0]
  else
    previous.concat remaining[0]
  flattenKernel here, remaining[1..]

flatten = (array) ->
  flattenKernel [], array

runTests tests, flatten