Home > Computer Science, Programming > Imperative Arrays and Functional Lists

Imperative Arrays and Functional Lists

You can tell a lot about a programming language by the native data structures it has. The main division of primary data structures seems to be between imperative and functional programming languages.

Imperative languages use arrays, with elements held in consecutive memory addresses. Lookup is efficient but insertion is slow. Functional languages more often use lists, where insertion is fast but lookup is slow. It seems interesting that there are these differences in fundamental data structures between imperative and functional languages. So why the difference?

Imperative languages are systematic. They follow a series of instructions in order. Arrays are optimal for imperative languages: different elements can easily be accessed and changed whenever necessary. This can make a lot of things really easy, and a lot of other things really aggravating.

Functional languages, on the other hand, are less about following a series of instructions as they are about flowing in and out of different functions. Lists are optimal for functional programming for a variety of reasons. Perhaps the most obvious is that they are very easy to use with recursive functions: indeed, their very definition is recursive. Implementing the Quicksort algorithm, as well as other such algorithms, is much easier with lists than with arrays. The most intuitive implementation of Quicksort requires repeatedly splitting a data set in half. With lists this is easy, but with arrays there is no simple way to do it. (There is a faster way to sort an array, but it’s complicated.)

Lists are much better at adding elements, removing elements, and breaking into parts; but sometimes it is still useful to be able to mess with elements in the middle of an array. In a purely functional language, though, there is not much reason why you would need to do this. So each data structure is optimal for its own style of programming.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: