length of list at racket
Solution 1
Here's how I would systematically make a function to find the length of a list.
The final result will be
;; length : [Listof Element] -> Number
;; Produces the number of elements in the list
(define (length lst)
(cond
[(empty? lst) 0]
[(cons? lst) (+ 1 (length (rest lst)))]))
But the more important thing is the systematic process, that you can use to write many more programs. The process I use here is the Design Recipe explained in the book How to Design Programs.
1: What is a list?
A list is either empty, or it's the combination of the first element with the rest of the elements. This "rest" is another list.
In Racket, "empty" is written as '()
, and "combine" for lists is written as cons
.
A [Listof Element] is one of:
- '()
- (cons Element [Listof Element])
Some examples of lists:
'() ; empty
(cons "I'm alone" '()) ; one element "I'm alone"
(cons "Hello" (cons "there" '())) ; two elements "Hello" and "there"
(cons 1 (cons 3 (cons 5 (cons 7 (cons 9 '()))))) ; five elements, odd numbers
2: What does length
do?
The length
function takes a list and produces a number representing the number of elements in the list. The empty list as length 0
, and the examples above should have lengths 0
, 1
, 2
, and 5
.
;; length : [Listof Element] -> Number
;; Produces the number of elements in the list
;; (length '()) = 0
;; (length (cons "I'm alone" '())) = 1
;; (length (cons "Hello" (cons "there" '()))) = 2
;; (cons 1 (cons 3 (cons 5 (cons 7 (cons 9 '()))))) = 5
(define (length lst)
???)
3: What are the cases in the definition?
A list is either empty or a cons. To test whether its empty, we can use a cond
with the question (empty? lst)
for the empty case, and the question (cons? lst)
for the cons case.
(define (length lst)
(cond
[(empty? lst) ???]
[(cons? lst) ???]))
4: What "sub-pieces" of the data are available in each case?
An empty list has no sub-pieces.
However, a (cons Element [Listof Element])
has two sub-pieces:
- the first thing,
Element
, - and the rest of the list,
[Listof Element]
.
To get these in racket, you can use first
and rest
respectively.
(define (length lst)
(cond
[(empty? lst) ???]
[(cons? lst) ... (first lst) ... (rest lst) ...]))
5: Are any of those sub-pieces complex data?
The (first lst)
is just an Element
. For the purposes of length
, it's not complex, and we don't have to process it further.
The (rest lst)
is another [Listof Element]
though, and that is complex. How do we deal with that? By using a helper function.
In this case, we want a helper function that's length-related, and takes a [Listof Element]
as an argument. In this case, that helper function happens to be length
, the function we're currently defining! We can use it recursively on (rest lst)
because it's a smaller sub-piece.
(define (length lst)
(cond
[(empty? lst) ???]
[(cons? lst) ... (first lst) ... (length (rest lst)) ...]))
6: Fill in the holes, using both your intuition of how length should work, and the examples we wrote before
The first example (length '()) = 0
tells us that the first ???
hole should be filled with 0
.
(define (length lst)
(cond
[(empty? lst) 0]
[(cons? lst) ... (first lst) ... (length (rest lst)) ...]))
The second hole, the ...
s around the first and the length of the rest, is harder. But your intuition about length should tell you that the length of a "combined" list of first and rest should be one plus the length of the rest. Turing that into code:
(define (length lst)
(cond
[(empty? lst) 0]
[(cons? lst) (+ 1 (length (rest lst)))]))
The systematic steps I used are explained in the book How to Design Programs.
Solution 2
You'll need to think in Scheme. If you already know a programming language it will not help you in the beginning.
(define (my-lenght lst) ; lst is the list argument
(if (null? lst) ; call function null? to check for empty list
0 ; an empty list has zero i length
(+ 1 ; length is one more
(my-length (cdr lst))))) ; than the list with first element omitted
Here is how to call the function
(my-lenght '(1 2 3)) ; ==> 3
If you look at your code you called len
as a function. Function names are just variables pointing to function objects so +
is a variable and (+ a b)
is code with 3 variables. One that becomes a function and the two other becomes numbers.
danny lee
Updated on June 14, 2022Comments
-
danny lee almost 2 years
I was trying to figure out getting the length of the list
but failed to do so
showing
expected: number? given: #<procedure:list> argument position: 1st other arguments...:
my code:
(define (length len) (list '(1 2 3 4 5 6 7)) (if (= list null) (len) (cdr list) ) (+ len 1) (length) ) (length 0)
What I was intending to do is
- get the list(which is inside it, because cannot figure out how to get list...)
- make 'if' function so that it can
printf len
if the (cdr list) become null
if you guys have any errors just let me know, please
I was trying to study Racket about a 2 weeks ago and couldn't figure out how to do it...
thanks!