Lecture overview -- Keyboard shortcut: 'u'  Previous page: Some simple and general higher-order functions -- Keyboard shortcut: 'p'  Next page: Generation of list selectors -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Lecture 2 - Page 15 : 35
Programming Paradigms
Recursion and Higher-order Functions
Linear search in lists

Search criterias can be passed as predicates to search functions

;; A simple linear list search function.
;; Return the first element which satisfies the predicate pred.
;; If no such element is found, return #f.
(define (find-in-list pred lst)
  (cond ((null? lst) #f)
        ((pred (car lst)) (car lst))
        (else (find-in-list pred (cdr lst)))))

A linear list search function. A predicate accepts as input an element in the list, and it returns either true (#t) or false (#f). If the predicate holds (if it returns true), we have found what we searched for. The predicate pred is passed as the first parameter to find-in-list. As it is emphasized in blue color, the predicate is applied on the elements of the list. The first successful application (an application with true result) terminates the search, and the element is returned. If the first case in the conditional succeeds (the brown condition) we have visited all elements in the list, and we conclude that the element looked for is not there. In that case we return false.

c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/find-in-list-sessionA sample interaction using find-in-list.

We define a simple association list which relates persons (symbols) and hair colors (strings). The third interaction searches for per's entry in the list. The fourth interaction searches for a person with pink hair color. In the fifth interaction nothing is found, because no person has yellow hair color. In the sixth interaction we illustrate the convenience of boolean convention in Scheme: everything but #f counts as true. From a traditional typing point of view the let expression is problematic, because it can return either a person (a symbol) or a boolean value. Notice however, from a pragmatic point of view, how useful this is.

Go to exerciseLinear string search
Go to exerciseIndex in list
Go to exerciseBinary search in sorted vectors
Go to exerciseGenerating a C-style compare function
Go to exerciseHigher-order functions in 'Functional Programming Languages'