Python implementation of lists, as approached by bootstrapworld.org / How to Design Programs -- that is as an "algebraic data type".

lists-algebraic.py

# Data definition: A list is either
#  - [], OR
#   put( {someItem}, {someList} )     (that is: one item "put" onto the front of some existing (slightly shorter) list)



#### helper functions for lists (which we represent internally as the python-builtin-list-type, unsurprisingly).

# put: T, list<T> → list<T>     (constructor)
# Construct a new list, by adding one item to the front of an existing list
def put(frst,rst): return [frst]+rst    # turn our def'n into python's built-in list


# first: list<T> → T            (getter)
# return the first item in a non-empy list `lst`
def first(lst): return lst[0]

# rest : list<T> → list<T>      (getter)
# return everything in `lst` BUT the first element
def rest(lst): return lst[1:]



#### template 

## general template for ANY function processing a list (follows from its data-definition):
##
#def funcForList( someLst ):
#    if someLst==[]:
#        return ____
#    else:
#        return ___first(someLst)___funcForList(rest(someLst))_____



#### an example of writing a list-processing function.  (Python requires we write this *before* our tests.)

# count the number of times "hi" occurs in `words`
def countHellos(words):
    if words==[]:
        return 0
    else:
        return (1 if first(words)=="hi" else 0) + countHellos(rest(words))

    
# tests, to be written BEFORE writing the code.  Low-brow framework: just `assert .. == ..`
# 
assert 0 == countHellos([])
assert 1 == countHellos(["hi"])             # build ans from: "hi",  0 = countHellos([])
assert 0 == countHellos(["bye"])            # build ans from: "bye", 0 = countHellos([])
assert 1 == countHellos(["bye","hi"])       # build ans from: "bye", 1 = countHellos(["hi"])
assert 1 == countHellos(["hi","bye"])       # build ans from: "hi",  0 = countHellos(["bye"])
assert 2 == countHellos(["hi","bye","hi"])  # build ans from: "hi",  1 = countHellos(["bye","hi"])
#
# where `["hi","bye"]` is shorthand for `put("hi", put("bye", []))`
# When first teaching students, I'd write the long-hand form, to 
#   (a) remind us that a constructed-list is an object with exactly two fields, 
#   (b) we are following the exact same approach we did for earlier (non-recursive) objects/structs.



# When writing EACH test for non-empty, first fill in this "worksheet":
#   a.  words = _______
#   b.  first(words) = _______
#   c.  rest(words) = _______
#   d.  countHellos(rest(words)) = _______
# After we write the tests, now write a formula for the general-case, combining only (b) and (d)
#
# We do this because of the list data-def'n:  a list is either empty, or it has a first/rest;
#    the `first` is a string so call a pertinent helper-function on it (in this case `...=="hi"`)
#    the `rest` is a list-of-string so call a pertinent helper-function on it (in this case `countHellos`)