functional programming - Flattening a List of Lists -

i'm new scheme , functional programming in general. can explain code — kons , knil are? goal flatten list of lists.

(define (fold1 kons knil lst)     (if (null? lst)         knil         (fold1 kons (kons (car lst) knil) (cdr lst)))) 

i'm kons function it's being applied 2 arguments still not totally sure functionality.

this (weird) fold

this generalized folding procedure. in lisps, lists represented cons cells , empty list, each (proper) list either empty list (), or cons cell car element of list , cdr rest of list. e.g., list (1 2 3 4 5) can produced by

(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '()))))) 

the fold1 function you've shown:

(define (fold1 kons knil lst)   (if (null? lst)       knil       (fold1 kons (kons (car lst) knil) (cdr lst)))) 

is a way of taking list 1 shown above , transforming to:

(kons 5 (kons 4 (kons 3 (kons 2 (kons 1 knil))))) 

this fold. efficient generalization of lots of operations. instance, if use 0 knil , + kons, compute sum of elements in list.

usually folds right or left associative. proper left-associative fold transform

(kons (kons (kons (kons (kons knil 1) 2) 3) 4) 5) 

which might clearer when viewed + , infix notation:

(((((0 + 1) + 2) + 3) + 4) + 5) 

the right associative fold become

(1 + (2 + (3 + (4 + (5 + 0))))) 

the left associative fold can more efficient because natural implementation tail recursive, , elements consumed list in order can extracted list. e.g., in proper left associatve example, (kons knil 1) can evaluated first produce value v, , then, in same stack space, (kons v 2) can evaluated, , on. right associative method requires traversing end of list first. naïve implementation requires stack space proportional length of list.

this fold1 mixes things bit, because it's processing elements of list in left associative manner, order of arguments combining function reversed.

this type of definition can used time have algebraic datatype. since list in lisps either empty list, or element , list combined cons, can write function handles each of these cases, , produces new value “replacing” cons combination function , empty list designated value.

flattening list of lists

so, if you've got list of lists, e.g., ((a b) (c d) (e f)), it's constructed

(cons '(a b) (cons '(c d) (cons '(e f) '()))) 

with right associative fold, transform to:

(append '(a b) (append '(c d) (append '(e f) '()))) 

by using append kons, , '() knil. however, in mixed fold, structure be

(kons '(e f) (kons '(c d) (kons '(a b) knil))) 

so knil can still '(), kons need function calls append, swaps argument order:

(define (flatten lists)   (fold1 (lambda (right left)            (append left right))          '()          lists)) 

and have:

(flatten '((a b) (c d) (e f))) ;=> (a b c d e f) 

flattening deeper lists of lists

given folding exercise, expected list of lists nested 1 layer deep. however, since we've seen how implement simple flatten

(define (flatten lists)   (fold1 (lambda (right left)            (append left right))          '()          lists)) 

we can modify make sure deeper lists flattened, too. kons function now

(lambda (right left)   (append left right)) 

simply appends 2 lists together. left appended , flattened list we've been building up. right new component we're taking on now. if make call flatten that, too, should flatten arbitrarily nested lists:

(define (flatten lists)   (fold1 (lambda (right left)            (append left (flatten right)))  ; recursively flatten sublists          '()          lists)) 

this almost right, except when call (flatten '((a b) (c d))), we'll end making call (flatten '(a b)), in turn make call (flatten 'a), flatten wrapper fold1, , fold1 expects arguments lists. need decide when flatten called non-list. simple approach have return list containing non-list argument. return value mesh nicely append that's receiving value.

(define (flatten lists)               ; lists not list of lists anymore,    (if (not (pair? lists))             ; perhaps better name should chosen       (list lists)       (fold1 (lambda (right left)                (append left (flatten right)))              '()              lists))) 

now have

(flatten '(a (b (c)) (((d))))) ;=> (a b c d)