How to concatenate all the elements of the argument lists into a single list

Question

I am trying to concatenate all elements in the list argument into a single list. I have this code:

(define (concatenate . lsts)
 (let rec ([l lsts]
          [acc '()])
   (if (empty? l)
       acc
       (rec (cons (list* l)
                 acc)))))

An example of output is here:

 > (concatenate '(1 2 3) '(hi bye) '(4 5 6))
 '(1 2 3 hi bye 4 5 6)

But I keep getting this error:

 rec: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1

Can someone please explain this?

Answer 1

Assuming you are allowed to call append, for simplicity. You have

(define (concatenate . lsts)
 (let rec ([l lsts]
          [acc '()])
   (if (empty? l)
       acc
       (rec (cons (list* l)  ; only ONE
                  acc)       ; argument
            ))))

calling rec with only one argument. I have added a newline there so it becomes more self-evident.

But your definition says it needs two. One way to fix this is

(define (conc . lsts)
 (let rec ([ls lsts]
           [acc '()])
   (if (empty? ls)
       acc
       (rec (cdr ls)               ; first argument
            (append acc (car ls))  ; second argument
            ))))

Now e.g.

(conc (list 1 2) (list 3 4))

; => '(1 2 3 4)

I used append. Calling list* doesn't seem to do anything useful here, to me.

---

(edit:)

Using append that way was done for simplicity. Repeatedly appending on the right is actually an anti-pattern, because it leads to quadratic code (referring to its time complexity).

Appending on the left with consequent reversing of the final result is the usual remedy applied to that problem, to get the linear behavior back:

(define (conc2 . lsts)
 (let rec ([ls lsts]
           [acc '()])
   (if (empty? ls)
       (reverse acc)
       (rec (cdr ls)
            (append (reverse (car ls))
                    acc)))))

This assumes that append reuses its second argument and only creates new list structure for the copy of its first.

The repeated reverses pattern is a bit grating. Trying to make it yet more linear, we get this simple recursive code:

(define (conc3 . lols)
  (cond
    [(null? lols) empty ]  
    [(null? (car lols)) 
       (apply conc3 (cdr lols)) ] 
    [else
       (cons (caar lols)
             (apply conc3
                    (cons (cdar lols) (cdr lols))))]))

This would be even better if the "tail recursive modulo cons" optimization was applied by a compiler, or if cons were evaluated lazily.

But we can build the result in the top-down manner ourselves, explicitly, set-cdr!-ing the growing list's last cell. This can be seen in this answer.

Answer 2

Another answer explains the OP error, and shows how the code can be fixed using append. But there could be reasons for append to be disallowed in this assignment (of course, it could be replaced with, for example, an inner "named let" iteration).

This answer will present an alternative approach and describe how it can be derived.

#lang racket
(require test-engine/racket-tests)

(define (conc . lols) ;; ("List of Lists" -> List)
  ;; produce (in order) the elements of the list elements of lols as one list
  ;; example: (conc '(1 2 3) '(hi bye) '(4 5 6)) => '(1 2 3 hi bye 4 5 6)
  (cond
    [(andmap null? lols) empty ]   ;(1) => empty result
    [else
     (cons (if (null? (car lols))  ;(2) => head of result
               (car (apply conc (cdr lols)))
               (caar lols))
           (apply conc             ;(3) => tail of result
                  (cond
                    [(null? (car lols))
                     (list (cdr (apply conc (cdr lols)))) ]
                    [(null? (cdar lols))
                     (cdr lols) ]
                    [else
                     (cons (cdar lols) (cdr lols)) ]))) ]))

(check-expect (conc '() )           '())
(check-expect (conc '() '() )       '())
(check-expect (conc '(1) )          '(1))
(check-expect (conc '() '(1) )      '(1))
(check-expect (conc '() '(1 2) )    '(1 2))
(check-expect (conc '(1) '() )      '(1))
(check-expect (conc '(1) '(2) )     '(1 2))
(check-expect (conc '(1 2) '(3 4) ) '(1 2 3 4))
(check-expect (conc '(1 2 3) '(hi bye) '(4 5 6)) '(1 2 3 hi bye 4 5 6))

(test)

Welcome to DrRacket, version 8.6 [cs].
Language: racket, with debugging; memory limit: 128 MB.
All 8 tests passed!
> 

How was this code derived?

"The observation that program structure follows data structure is a key lesson in introductory programming" [1]

A systematic program design method can be used to derive function code from the structure of arguments. For a List argument, a simple template (natural recursion) is often appropriate:

(define (fn lox) ;; (Listof X) -> Y                  ; *template*
  ;; produce a Y from lox using natural recursion    ;
  (cond                                              ;
    [(empty? lox) ... ]  #|base case|# ;; Y          ;
    [else (...           #|something|# ;; X Y -> Y   ;
            (first lox) (fn (rest lox))) ]))         ;

(Here the ...s are placeholders to be replaced by code to create a particular list-argumented function; eg with 0 and + the result is (sum list-of-numbers), with empty and cons it's list-copy; many list functions follow this pattern. Racket's "Student Languages" support placeholders.)

Gibbons [1] points out that corecursion, a design recipe based on result structure, can also be helpful, and says:

For a structurally corecursive program towards lists, there are three questions to ask:

1. When is the output empty?
2. If the output isn’t empty, what is its head?
3. And from what data is its tail recursively constructed?

So for simple corecursion producing a List result, a template could be:

(define (fn x) ;; X -> ListOfY
  ;; produce list of y from x using natural corecursion
  (cond
    [... empty]           ;(1) ... => empty
    [else (cons ...       ;(2) ... => head
           (fn ...)) ]))  ;(3) ... => tail data

Examples are useful to work out what should replace the placeholders:

the design recipe for structural recursion calls for examples that cover all possible input variants, examples for co-programs should cover all possible output variants.

The check-expect examples above can be worked through to derive (1), (2), and (3).

[1] Gibbons 2021 How to design co-programs