Insertion sort (Io)

From LiteratePrograms

Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET

Here the first entry for Io. This language is quite remarkable in that it claims to have no keywords, even things like loop, ifs etc are build on other things. In that it's quite remarkable and "simple", but getting used to it will surely take some time. Here's now an implementation of the insertion sort, borrowed from Smalltalk and Lisp:

List do (
  insertionSort := method(cmpBlock,
      j := 0
      for (index, 0, (size-1),
        el := at(index)
        j = index - 1
        # cmpBlock println
        while (j >= 0, 
          if ((cmpBlock call(at(j), el)),
            break,
            # else
            swapIndices(j+1, j)
          )
          j = j -1 
        )
        atPut(j+1, el)
      )
    ) 
  )

Io is based on Prototyps and one of the standard implemented one is List. With List do do I add something new to the Prototyp. The name List is AFAIKT misleading because it's not a list but an extensible Array. In Io the use of ( is quite important and used different as in other language I've had the luck to visit.

You can see that a new Function/Method is added because of the insertionSort := method . The method in this case take on parameter the cmpBlock. According to http://www.quag.geek.nz/io/getting-started/executable-args is my usage of block unusual here, however I found it fits nicely with the Smalltalk and/or Ruby solution.

One think which is a bit different to other language is that you have on operator to "introduce" new variable and one to set it's value if it's a known variable; := is for declaring a new variabel which in the first case is part of List (and a method) and j:= 0 just introduced a new Counter.

Io has different kinds of loops, In the first case it's for (index, 0, (size-1), at first a new variable is introduced which I called index, the next number is the initial number (0 here), which shows that counting in Io is zero based. But now from where comes (size-1). This is a function call on the Prototyp of List because I'm in the context of List (remember the do) this sends a message to self, so I could have written (self size) - 1. But the self is not needed because of the context.

However seeing it strictly the way of calling a function is always: Object message in this part Io is equal to Smalltalk (but there you alway must include the Object you're working on first)

Blocks are also simple Objects which one can run functions on in our example it's cmpBlock call(at(j), el)

We just can see here that cmpBlock is supposed to be a "method" of two parameters. The rest of the whole program is similiar to all the other programs. Now there's just one thing left: Calling this new function:

tList := list (1,3,5,10,-1,-29,20)
tList println
tList insertionSort(block(a,b, a < b))
tList println

Here's the output:

 io insertion_sort.io
list(1, 3, 5, 10, -1, -29, 20)
list(-29, -1, 1, 3, 5, 10, 20)

Seems to be ok ;-)

Io is on of the many language jewels out there, feel free to try it yourself.

Download code