wiki:Functions/Length

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.