# Differences between for/fold and explicit car/cdr recursion? **URL:** \ **Category:** Questions & Answers\ **Created:** [August 9, 2025, 3:07pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891 "2025-08-09T15:07:41Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 9, 2025, 3:07pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/1 "2025-08-09T15:07:41Z")
I solved one of the katas on codewars: it's called ["are they the same?"](https://www.codewars.com/kata/550498447451fbbd7600041c). The key thing is deciding if two lists have equal elements. My solution used `for/fold`; one of the other solutions used `first` and `rest` and explicitly recursed. I'm wondering about the basic conceptual difference between these two functions: ```scheme (define (all-equal-via-fold xs ys) (for/fold ([all-equal #t]) ([x xs] [y ys] #:break (not all-equal)) (and all-equal (equal? x y)))) (define (all-equal-via-cons-and-cdr xs ys) (if (equal? (first xs) (first ys)) (all-equal-via-cons-and-cdr (rest xs) (rest ys)) #f)) ``` (Those aren't exactly what is used in the problem/kata, but they illustrate what I'm wondering; you can imagine replacing `equal?` in `(equal? x y)` and `(equal? (first xs) (first ys))` with some other predicate.) Is there a meaningful difference between those two? I know there are a lot of extra details involved in the `for/fold`, but I want to verify my mental model here: I _think_ that the fold, with its `#:break`, will get compiled into something equivalent to the explicit first/rest recursion: for each thing over which we are folding (an x and y pair), it runs the predicate, uses the result to update the accumulator (or break out of the fold), and then proceeds to do the same thing on the rest of the thing over which we are folding. That seems to match conceptually with the recursion: take the first x and y pair in the lists, run the predicate, and then either return (= break out of the fold) or recurse (= "do the same thing on the rest of the thing..."). On a basic conceptual level, am I right that these are pretty much equivalent? If so, what differences are there between the two? ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 9, 2025, 3:17pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/2 "2025-08-09T15:17:27Z")
FWIW, some naive timing shows that the explicit recursion is about 40% faster than the fold version. So there's a practical difference here, which isn't so surprising. What else is relevant here? ```scheme (define (compare-times n) (let* ([length 1000] [xs (randlist length)] [ys (map sqr xs)]) (printf "fold:\n") (time (for ([_ (range n)]) (all-equal-via-fold xs ys))) (printf "recurse:\n") (time (for ([_ (range n)]) (all-equal-via-cons-and-cdr xs ys))))) ``` (`randlist` just makes a big list of random floats) And I get: ```scheme > (foo 100000000) fold: cpu time: 9912 real time: 9912 gc time: 0 recurse: cpu time: 6026 real time: 6026 gc time: 2 > ``` ---
**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\ **Post date:** [August 9, 2025, 5:22pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/3 "2025-08-09T17:22:09Z")
> [@ddrake](#): > > The key thing is deciding if two lists have equal elements. Both versions seem broken, and, even if this counterexample breaks what was supposed to be an unchecked invariant, the two implement different behavior: ```scheme > (all-equal-via-fold '(1 2) '(1 2 3)) #t > (all-equal-via-cons-and-cdr '(1 2) '(1 2 3)) first: contract violation expected: (and/c list? (not/c empty?)) given: '() [,bt for context] ``` (Your original question is a good one, I just didn't want to “spoil” a puzzle by jumping over this way the two differ.) ---
**Author:** ![greghendershott](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/greghendershott/32/98_2.png) [@greghendershott](https://racket.discourse.group/u/greghendershott)\ **Post date:** [August 9, 2025, 7:31pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/4 "2025-08-09T19:31:37Z")
As for performance: When you know you'll be operating on a specific type of sequence -- like a list -- you want to give `for` that "hint" -- like by using `in-list`. See [Iteration Performance](https://docs.racket-lang.org/guide/for.html#(part._for-performance)). I think the only time I'd omit that is when the code is supposed to be "generic" for any type of sequence (which in my experience is rare), or, when I'm casually exploring or experimenting with short sequences in the REPL and performance doesn't matter. With `in-list` I'd expect the `for/fold` code to expand into something much like the handwritten recursion (but corrected for details like @LiberalArtist pointed out). * * * FWIW I'd probably use `for/and` unless that would be cheating for the kata. (To really _really_ cheat, I'd give as the solution just `(define comp equal?)` 😃 IIUC the problem correctly. But seriously, it's interesting to think about how you would define `equal?` for real, over a variety of values.) ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 9, 2025, 9:51pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/5 "2025-08-09T21:51:16Z")
Ah, that's an artifact of me trying to extract just the relevant piece of the full solution -- the assumption is that the lists are of the same length. In the actual recursive solution, that is handled. My own solution -- which was accepted as correct on the codewars site 😲 -- has that bug, because `for/fold` terminates on the shorter input. I commented on the solution and suggested they add tests to exercise that corner case. Thanks for that! So, for the moment, let's just assume that the lists are the same length. The differing behavior, I think, is a good example of a meaningful difference between the fold and the recursion: the fold just automatically terminates on the shorter input; the recursion blows up. In some situations, the former behavior may be exactly what you want. But not here... ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 9, 2025, 11:00pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/6 "2025-08-09T23:00:10Z")
> [@greghendershott](#): > > With `in-list` I'd expect the `for/fold` code to expand into something much like the handwritten recursion (but corrected for details like @LiberalArtist pointed out). Indeed, that eliminates the performance difference -- I just ran the same timing, and there's no significant difference. ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 9, 2025, 11:03pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/7 "2025-08-09T23:03:52Z")
> [@greghendershott](#): > > I'd probably use `for/and` unless that would be cheating for the kata. It's not, and I didn't know about `for/and` -- it's precisely what I was aiming to do with my fold. ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 10, 2025, 6:55pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/8 "2025-08-10T18:55:09Z")
BTW, is there a nice idiomatic way to get `for/fold` and friends to somehow signal or handle the situation in which one of the iteration sequences is exhausted, but the other isn't? It looks like `for`'s essential behavior is to just terminate on the shorter sequence, and I don't see a reasonable way to detect or signal that situation. I asked a couple chatbots for some code, and both landed on something sequence-\>generator -- but when I really looked at the code, it seemed to be (for this problem, at any rate) just a really fancy complex version of that simplistic first/rest recursion. ---
**Author:** ![greghendershott](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/greghendershott/32/98_2.png) [@greghendershott](https://racket.discourse.group/u/greghendershott)\ **Post date:** [August 10, 2025, 7:57pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/9 "2025-08-10T19:57:52Z")
No, I don't think so. The iteration/comprehension forms like `for/fold` follow the example of `fold` and `map` in this regard. If I needed special behavior, I would probably just write out a recursive function by hand. For example, as a first attempt: ```scheme (define (strict-map f as bs) (cond [(and (pair? as) (pair? bs)) (cons (f (car as) (car bs)) (strict-map f (cdr as) (cdr bs)))] [(and (null? as) (null? bs)) null] [else (error 'strict-map "lists are different lengths")])) ``` Or, using `racket/match` something like: ```scheme (define (strict-map f as bs) (match* [as bs] [[(cons a as) (cons b bs)] (cons (f a b) (strict-map f as bs))] [[(list) (list)] null] [[_ _] (error 'strict-map "lists are different lengths")])) ``` When writing recursive functions by hand I tend to prefer pattern matching. Because it reduces the `car` and `cdr` noise:signal ratio. And because it looks like writing out the various cases in a "by example" style. And, as with `for/fold`, it tends to expand to equivalently efficient code. p.s. That `strict-map` could be rewritten to be fully variadic just like `map`. ---
**Author:** ![EmEf](https://avatars.discourse-cdn.com/v4/letter/e/53a042/32.png) [@EmEf](https://racket.discourse.group/u/EmEf)\ **Post date:** [August 10, 2025, 8:59pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/10 "2025-08-10T20:59:18Z")
Here is a way to get you started on a "cheaply constructed but expensive" `for/fold` variant that protects you from sequences of unequal length: ```scheme #lang racket (require (for-syntax syntax/parse)) (define-syntax (for/fold/protected stx) (syntax-parse stx [(_ accu ([x xx] ... clauses ...) body ...) #:with (determine-length ...) (protect #'(xx ...)) #'(cond [(not (= (determine-length xx) ...)) (error 'for/fold/protect "expected sequences of equal length, given ~a" `[xx ...])] [else (for/fold accu ([x xx] ... clauses ...) body ...)])])) (define-for-syntax (protect syn-lists) (define lists (syntax->list syn-lists)) (for/list ([l lists]) (syntax-parse l [((~literal in-list) l) #'stream-length] [((~literal in-vector) v) #'sequence-length] ;; the next line is wrong [_ #'length]))) (define ll '(1 2 3)) (define kk '#(a b c d)) (define mm '(1 2 3)) (for/fold/protected ([r '()] #:result (reverse r)) ([l (in-list ll)] [m mm] [k (in-vector kk)] #:do [(printf "~a ~a\n" l k)]) (cons (list m l k) r)) ``` You'd have to write a generic `length-for` to get the "wrong" case done properly. The "cheap" refers to the macro part. The "expensive" refers to the upfront checking part, which duplicates the traversal. When I program, I use `fold` when I don't know the length and want an "inexpensive" way of failing (terminating the program execution) and `for/fold` when I am okay with abandoning left-over elements of a sequence (or when I know they are guaranteed to be of the same length). ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 11, 2025, 12:28pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/11 "2025-08-11T12:28:05Z")
> [@greghendershott](#): > > When writing recursive functions by hand I tend to prefer pattern matching. Because it reduces the `car` and `cdr` noise:signal ratio. And because it looks like writing out the various cases in a "by example" style. "Learn about Racket's pattern matching" has been on my radar, thank you for prompting me to learn a bit about it. This approach is lovely! It's so short and so readable. The pattern matching style really appeals to me; as you say, it's nice to describe cases via "shapes" or examples or declaratively, rather than interrogatively with predicates. Here, it's a perfect description of what I want: the first pattern says "the shape is that of two lists that have at least one element"; the second says "two empty lists"; and the third says "in any other situation, we have an empty and a nonempty list". And not only that, but when I use that for my solution to the kata, it's 35% faster than the explicit car/cdr solution! I have no idea why. Here's my solution: ```scheme (define (comp%% xs ys) (let recurse ([xs (sort (map sqr xs) <)] [ys (sort ys <)]) (match* [xs ys] [[(cons a as) (cons b bs)] (if (equal? a b) (recurse as bs) #f)] [[(list) (list)] #t] [[_ _] #f]))) ``` and comparing that to [the explicit car/cdr solution](https://www.codewars.com/kata/reviews/5cd519c073a71300012316e6/groups/6104b910d9d0b80001a734a8), mine runs faster. Now my question is, why? I tested, and it's not the explicit length checks. My named let defines a function that seems equivalent to the "`compAux`" function in the other solution. But mine is significantly faster. Any ideas why? (Another question: I'm not clear on the difference between `match` and `match*`. I read the reference, but it's not so clear to my little pea brain.) ---
**Author:** ![greghendershott](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/greghendershott/32/98_2.png) [@greghendershott](https://racket.discourse.group/u/greghendershott)\ **Post date:** [August 11, 2025, 12:56pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/12 "2025-08-11T12:56:18Z")
Sorry, using `match*` here was probably an unnecessary distraction. (Unlike many people here, I am definitely **not** a professional educator.) `match*` is just a convenience for `match`. For now just think of it as writing e.g. `(match (list as bs) _)` and wrapping each pattern clause in a `list`. * * * By the way, I'm pretty sure I first saw this style -- "classic" handwritten recursion but using `match` -- in some code by @soegaard, to give credit where it's due. 🙂 ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [August 11, 2025, 11:34pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/13 "2025-08-11T23:34:28Z")
> [@greghendershott](#): > > `match*` is just a convenience for `match`. For now just think of it as writing e.g. `(match (list as bs) _)` and wrapping each pattern clause in a `list`. That seems roughly right: these work the same, as far as I see: ```scheme (define (match-no-star xs ys) (match (list xs ys) [(list (cons a as) (cons b bs)) '2-element-lists] [(list empty empty) 'empty-empty] [(list as bs) (printf "something else: ~s, ~s\n" as bs)])) (define (match-no-star-lotsa-punctuation xs ys) (match `(,xs ,ys) [`( ,(cons a as) ,(cons b bs)) '2-element-lists] [`(,empty ,empty) 'empty-empty] [`(,as ,bs) (printf "something else: ~s, ~s\n" as bs)])) (define (match-star xs ys) (match* (xs ys) [((cons a as) (cons b bs)) '1+-element-lists] [(empty empty) 'empty-empty] [(as bs) (printf "something else: ~s, ~s\n" as bs)])) ``` ---
**Author:** ![greghendershott](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/greghendershott/32/98_2.png) [@greghendershott](https://racket.discourse.group/u/greghendershott)\ **Post date:** [August 12, 2025, 1:50pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/14 "2025-08-12T13:50:04Z")
> [@ddrake](#): > > and comparing that to [the explicit car/cdr solution](https://www.codewars.com/kata/reviews/5cd519c073a71300012316e6/groups/6104b910d9d0b80001a734a8), mine runs faster. > > Now my question is, why? I tested, and it's not the explicit length checks. My named let defines a function that seems equivalent to the "`compAux`" function in the other solution. But mine is significantly faster. Any ideas why? I dodged this part. Not immediately sure why. Might be related to details like this `let` and comment from the source for Racket's `map`: ```scheme (let loop ([l l]) (cond [(null? l) null] [else (let ([r (cdr l)]) ; so `l` is not necessarily retained during `f` (cons (f (car l)) (loop r)))])) ``` The `match` approach also does that -- rebinds `as` to `(cdr as)`, ditto for `bs` -- and avoids that retention. This guess is more plausible if Racket's `time` says the extra time for your explicit `car`/`cdr` variation is mostly "GC". Having said all that, this guess feels insufficient? * * * p.s. Tip: When using Racket's `time` in code, run that using `racket` from the command-line. (If instead the code is run in e.g. DrRacket or Emacs Racket Mode, the timing is likely to be contaminated by other stuff running, as well if the code is annoated by errortrace for better stack traces, etc.) ---
**Author:** ![dstorrs](https://avatars.discourse-cdn.com/v4/letter/d/898d66/32.png) [@dstorrs](https://racket.discourse.group/u/dstorrs)\ **Post date:** [August 13, 2025, 9:10pm UTC](https://racket.discourse.group/t/differences-between-for-fold-and-explicit-car-cdr-recursion/3891/15 "2025-08-13T21:10:45Z")
> BTW, is there a nice idiomatic way to get `for/fold` and friends to somehow signal or handle the situation in which one of the iteration sequences is exhausted, but the other isn't? Not sure if this is what you want, but you could use a macro that checks the lengths before starting the fold: ```scheme #lang racket (require (for-syntax syntax/parse)) (define xs '(1 2)) (define ys '(1 2 3)) (define zs '(1 2 3)) (define-syntax (for/fold/same-length-lists stx) (syntax-parse stx [(_ xs:expr ys:expr) #'(and (= (length xs) (length ys)) (for/fold ([all-equal #t]) ([x xs] [y ys] #:break (not all-equal)) (and all-equal (equal? x y))))])) (for/fold/same-length-lists xs ys) (for/fold/same-length-lists ys zs) ```