CODEWITHSUNDEEP
schemerackethigher-order-functions
user3786933
user3786933

Reputation: 107

Any idea of how to interleave two lists in Dr Racket?

The problem is when lists have a different length, any idea of how to do it?

I have to use functions like map or something like that.

This is the code I wrote so far, it works with lists of the same length but it also needs to work with lists of different lengths:

(define (interleave list1 list2)
 (flatten 
   [map (lambda (x y) (cons x (cons y null)))
        list1 list2]))

When lists have different length this is the error that I get:

map: all lists must have same size; 
arguments were: #<procedure> '(1 2 3 4 5) '(a b c)

I'm trying to get (1 a 2 b 3 c 4 5) as the result here. Thank you.

Upvotes: 3

Views: 3289

Answers (5)

Will Ness
Will Ness

Reputation: 71119

"There ain't nothin' you can't not do with fold-right and some of them con-tin-uations thingies", said a cowboy to another, spittin' into the campfire and puffin' on his cigar in the evening, sippin' his black coffee from his rugged banged up tin mug. "Yessir, nothin' in the whole darn world."

(define (interleave xs ys)

    ;; interleave xs ys = foldr g n xs ys
    ;;    where
    ;;    g x r (y:ys) = x : y : r ys
    ;;    g x r []     = x : r []
    ;;    n ys         = ys

    ((foldr
       (lambda (x r)
         (lambda (ys) 
           (cond ((null? ys) (cons x (r '())))
                 (else (apply (lambda (y . ys)
                                 (cons x (cons y (r ys))))
                              ys)))))
       (lambda (ys) ys)
       xs)
     ys))

Illustration:

 interleave     [a,b,c]     [1,2,3,4,5]
 (foldr g n     [a,b,c])    [1,2,3,4,5]
 (g a  (foldr g n [b,c]))   [1,2,3,4,5]
 (g a        (g b (g c n))) [1,2,3,4,5]
 [a, 1,   ...(g b (g c n))    [2,3,4,5]]
 [a, 1, b, 2,  ...(g c n)       [3,4,5]]
 [a, 1, b, 2, c, 3, ...n          [4,5]]
 [a, 1, b, 2, c, 3,            ...[4,5]]
 [a, 1, b, 2, c, 3,                4,5 ]

 interleave       [a,b,c,d]      [1,2]
 (foldr g n       [a,b,c,d])     [1,2]
 (g a    (foldr g n [b,c,d]))    [1,2]
 (g a       (g b (g c (g d n)))) [1,2]
 [a, 1,  ...(g b (g c (g d n)))    [2]]
 [a, 1, b, 2, ...(g c (g d n))      []]
 [a, 1, b, 2, c,   ...(g d n)       []]
 [a, 1, b, 2, c, d,     ...n        []]
 [a, 1, b, 2, c, d,              ...[]]
 [a, 1, b, 2, c, d                    ]

Upvotes: 1

user1311045
user1311045

Reputation:

I'm assuming your desired behavior is that the lists are interleaved for as long as this is possible, and then whatever is left over from the nonempty list is appended to the end. In that case one possible implementation is

(define (interleave a b)
  (if (null? a)
      b
      (cons (car a)
            (interleave b (cdr a)))))

I think this is probably the simplest possible way to write what you're looking for.

Upvotes: 2

Penguino
Penguino

Reputation: 2186

A solution using simple list manipulation functions might be: 

 (define (interleave list1 list2)
   (cond ((empty? list1) list2)
         ((empty? list2) list1)
         (else 
          (append 
           (list (car list1) (car list2))
           (interleave (cdr list1) (cdr list2))))))

Testing...

 > (interleave '(1 2 3 4 5) '(a b c))
 (1 a 2 b 3 c 4 5)
 > (interleave '(1 2 3 4 5) '())
 (1 2 3 4 5)
 > (interleave '() '(a b c))
 (a b c)
 >

I think it is fairly self-documenting.

Upvotes: 1

soegaard
soegaard

Reputation: 31145

#lang racket

(define (weave xs ys)
  (match (list xs ys)
    [(list (cons x xs) (cons y ys)) (cons x (cons y (weave xs ys)))]
    [(list '() ys)                  ys]
    [(list xs '())                  xs]))

Upvotes: 3

Sylwester
Sylwester

Reputation: 48775

Neither map nor fold-right would work because they either signal an error when one list is smaller than the other or they tend to stop at the shortest list. eg. SRFI-1's map (interleave '(1 2 3 4) (circular-list 9 8)) ; ==> (1 9 2 8 3 9 4 8). For a different behavior you need to roll your own.

Upvotes: 1

Related Questions