COMP1811 Paradigms of Programming
Introduction to Lists in Scheme
Lists and pairs
Copyright By PowCoder代写 加微信 powcoder
• Importance of lists in Scheme/LISP.
– S-Expressions for lists (list)
– Operations on Lists (first, rest, length…)
– S-Expressions for pairing (cons) – Operations on pairs (car, cdr)
– The null object
– Non-empty lists as pairs.
• Defining symbols involving lists – constants
– functions
• Appendix:
– floating expressions: let
• Lists are key at Scheme/LISP*
– Object language level:
• Enumerating data
• Grouping data
*LISP comes from “List-Processor language”
• Implementing complex structures (trees…) – Metalanguage-level: (next lecture)
• Language itself modeled as data (homoiconic) • S-Expressions as (nested) lists of symbols
General notes
(list param**)
• list is a predefined procedure
• parameters: elements of list
• order matters
• Can be repeated • Elements can be
• Complex S-Expressions • no parameters: empty list
• Constant symbols – empty: ->list
• Total (always have sense)
– list?: val -> bool
– length: lst -> int
– append: lst lst -> lst
– empty?: lst -> bool
– equal?: lst lst -> bool
– cons: val lst -> lst
• Partial (may have no sense)
– first: lst -> elem
– rest: lst -> lst
– list-ref: lst int -> lst
Operations on lists
( cons param1 param2 )
You get a pair of two components
Pair operations.
– pair? : val -> bool
– car : pair -> val (first comp.)
– cdr : pair -> val. (second comp.)
Nemotenic “a” happens before “d”
Shortcuts :
• (car (cdr b)) -> (cadr b)
• (cdr (cdr b)) -> (cddr b)
• Under the hood…
– empty list is defined with value null.
– non-empty lists are defined as special pairs.
• 2nd component a list,
• 1st element an element.
• Therefore, non-empty lists supports
– Pair operations (cdr,car…)
– List operations (first, rest, length…)
() (cons 2 (cons 1 empty))
Lists as pairs
• Lists can be part of defines
– as constants
– in procedures*.
recursion lecture is coming soon
Defining/using symbols as lists
([ id1 exp1 ]
[ id2 exp2 ]
[ id_n exp_n ] ) expr )
It defines locally the symbols id1, id2, to be reused in the evaluation of expr
Variant let* allows you to reuse ids amont them
𝑑𝑥,𝑦 = (𝑥 −𝑥 )2+(𝑦 −𝑦 )2 2121
Floating expressions
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com