aquiline ascension .( Python vs Scheme: lists ).

published: 2010-11-16
author: Hans Nowak
tags:
python
python-vs-scheme
scheme

index
index by tag
about
homebase
blogroll

Python vs Scheme: lists

A few years ago I wrote a number of blog posts that compared features of Python (which I have known since ~1996) versus Chicken Scheme (which I was just getting into). As such, they are mostly written from the point of view of a Pythonista learning Scheme. Below are the links to the existing "Python vs Scheme" articles, in order of publication:

Function parameters (part I)
Function parameters (part II)
Formatted output
Simple list comprehensions
Dictionaries (I need to do a followup of this one, since it's really more Python dictionaries vs Scheme a-lists, and Chicken has hash tables as well)
Strings
Function parameters (part III)
Using files as both modules and programs

I figured that maybe it was time to continue this series. So here's the next installment: lists.

Both Python and Scheme have a native list type. Elements of lists can be of any type and can be mixed freely, unlike lists in statically typed languages, functional or otherwise.

That is pretty much where the similarities end, though. Lists in these two languages are implemented differently and often used differently.

Python's lists are basically resizable arrays. As a result, it's cheap to get a list's length, to append an element, or to access/rebind a list's item (all of these are O(1)). ¹

Perhaps surprisingly, inserting an element at the beginning of a list is O(N), because it's essentially a slicing operation that affects the whole list. According to Python in a Nutshell:

Rebinding a slice of length M1 with one of different length M2 is O(M1+M2+N1), where N1 is the number of items after the slice in the target list (in other words, such length-changing slice rebindings are very cheap when they occur at the end of a list, and costly when they occur at the beginning or around the middle of a long list).

By contrast, Scheme uses linked lists, like most (if not all) functional languages. More precisely, a list consists of cons cells or pairs. A list (a b c) is really a chain of pairs. ² (The relevant section in SICP explains it much better than I can, so I refer to that. :-) Also see below for other references.)

In any case, what you need to bear in mind if you're a Pythonista trying out Scheme, is that because of this implementation difference, performance differs as well.

Getting the first element of a Scheme list is very cheap; since the "list" is really a chain of pairs, and you already have the first pair, all you have to do is get the first element from it (using car). This is O(1).

Getting an element in the middle, or the last element, is O(N) though, because we need to traverse the list (chain of pairs), looking for the N-th element. This is not a matter of calculating an address and getting the value stored there, like an array.

For this reason, appending to the end of a list is expensive as well, and is therefore not done all that often. It's much more common to prepend an item to a list, which is as simple as (cons x lst). So, unlike Python, prepending an item is O(1), while appending it is O(N).

The difference doesn't matter much if you need to traverse a list (e.g. for a map or filter operation), but in some cases it forces you to write things differently. For example, when you have a loop in which you need to append to a list in each iteration, it is a common Scheme idiom to just "cons" the item to the accumulator list, and reverse that list when it is returned.

;; a version of map that uses this technique...

(define (my-map f lst)
  (define (my-map-aux lst acc)
    (if (null? lst)
        (reverse acc)
        (my-map-aux (cdr lst) (cons (f (car lst)) acc))))
  (my-map-aux lst '()))

(print (my-map - '(1 3 5 -10 0)))

Also, in Python it is more common to modify a list in-place. In Scheme this is not impossible or unusual, but it seems more common to use functions that produce new lists altogether. Due to the linked list implementation, creating a new list (by prepending a new item) is efficient, because all it requires is another cons cell.

Python lists are objects and therefore have methods (although there are a few built-in functions operating on them as well, like len()). In Scheme, you manipulate a list with functions; R5RS doesn't have a lot of those, so most Scheme implementations (including Chicken) implement SRFI-1, which adds dozens of new and useful functions. I will discuss this in more detail in a followup post.