# length

(define length (lambda (xs) (if (null? xs) 0 (+ 1 (length (cdr xs)))))

or

(define (length xs) (foldr (lambda (_ a) (+ 1 a)) 0 xs)))

tail-recursive, constant space

(define length (lambda (xs) (let recur ((xs xs) (a 0)) (if (null? xs) a (recur (cdr xs) (+ 1 a))))))

length [] = 0 length (x:xs) = 1 + length xs

length xs = lenAcc xs 0 lenAcc [] n = n lenAcc (_:ys) n = lenAcc ys (n+1)

O(2n)

length = sum . (map (const 1))

O(n)

length = foldr (\_ a -> a+1) 0

or in terms of the tail-recursive, constant-space foldl

length = foldl (\a _ -> a+1) 0

(define length X -> (length-h X 0)) (define length-h [] N -> N X N -> (length-h (tl X) (+ N 1)))

Last modified
4 years ago
Last modified on Nov 7, 2016, 1:01:43 PM

**Note:**See TracWiki for help on using the wiki.