Skip to content

Instantly share code, notes, and snippets.

@leppie
Created March 3, 2023 12:52
Show Gist options
  • Save leppie/83ba84b3e3c6c207310d0d6a0ed930be to your computer and use it in GitHub Desktop.
Save leppie/83ba84b3e3c6c207310d0d6a0ed930be to your computer and use it in GitHub Desktop.

IronScheme's Implementation of map

The actual implementation of map in IronScheme is as follows:

(define map
  (case-lambda 
    [(proc list1)
      (let f ((lst list1)(a '()))
        (if (null? lst)
            (reverse! a)
            (f (cdr lst) (cons (proc (car lst)) a))))]
    [(proc list1 . lists)
      (let ((orig-ls (cons list1 lists)))
        (let f ((lists orig-ls)(a '()))
          (if (all-empty? lists)
              (reverse! a)
              (call-with-values (lambda () (split lists 'map orig-ls))
                (lambda (cars cdrs)
                  (f cdrs (cons (apply proc cars) a)))))))]))

How it works

The implementation uses case-lambda to define two different versions of map. The first version takes a single procedure argument and a single list argument, while the second version takes a procedure argument and one or more list arguments.

The implementation uses a recursive function called f to apply the given procedure proc to each element of the input list(s) and accumulate the results. The first version of map simply calls f with the given list and an empty accumulator list.

The second version of map first combines all the input lists into a single list orig-ls using the cons procedure. It then calls f with orig-ls and an empty accumulator list.

The f function takes two arguments: lists, which is a list of the remaining input lists, and a, which is the accumulated result so far. If all the input lists are empty, f returns the accumulated result in reverse order using the reverse! procedure.

If any of the input lists are not empty, f uses the split procedure to separate the first elements of each non-empty input list into a list of cars and the remaining elements of each non-empty input list into a list of cdrs. The apply procedure is then used to apply the given procedure proc to the cars list, producing a single result. The cdrs list is then passed recursively to the next iteration of f, along with the accumulated result so far and the result of applying proc to cars.

The implementation uses a helper function called all-empty? to check whether all the input lists are empty. The split procedure is used to extract the first elements of each non-empty input list, while preserving the original order of the input lists.

Overall, this implementation of map uses a combination of recursive and iterative techniques to handle one or more input lists and apply a given procedure to each element, accumulating the results in a list. The use of reverse! ensures that the output list is in the same order as the input list(s).

Why does reverse! end with an exclamation mark?

In Scheme and many other programming languages, it is common to use an exclamation mark (!) at the end of a procedure name to indicate that the procedure has a side effect, meaning it modifies some state outside the procedure itself. In the case of reverse!, the exclamation mark indicates that the procedure modifies the order of elements in the input list in place, rather than creating a new list with the elements in reverse order.

In contrast, the non-destructive version of reverse that creates a new list with the elements in reverse order is simply

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment