1

My question is: how to write a procedure that utilises tailcall, and that constructs a list not in the reverse order. To show what I mean, here is an example of a very simple procedure that is iterative, and that creates a copy of a list:

(define (copy-list ls)
    (define (iter cp-ls rest-ls)
      (if (null? rest-ls)
          cp-ls
          (iter (cons (car rest-ls) cp-ls) (cdr rest-ls))))
    (iter '() ls))

The problem is that, due to the iterative order in which the elements are consed together, the returned list ends up reversed. Yes, you could easily solve this by doing (reverse cp-list) instead of just cp-list in the if-block, but the problem with this is that reverse is a recursive process. Utilising this procedure will nullify the tailcall advantage, which is that the stack size grows linearly with the input size.

So, basically, how to write a procedure like the one mentioned that returns the list in correct order without utilising any sort of recursive processes?

Thanks

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Snusifer
  • 485
  • 3
  • 17
  • 1
    Would changing `(iter '() ls)` to `(iter '() (iter '() ls))` work? – RowPJ Sep 10 '20 at 10:26
  • @RowPJ I dont care what anybody says, but thats actually kind of genius. Thanks – Snusifer Sep 10 '20 at 10:30
  • 2
    I don't think `reverse` is implemented as a recursive process, in fact I think it's implemented pretty much exactly as your `iter` procedure. So your procedure is basically doing `(reverse (reverse ls))`. If you're not mutating lists, it isn't actually necessary to "copy" them, it doesn't have any useful effect in your program. – Óscar López Sep 10 '20 at 12:10
  • 1
    the tailcall advantage is that the stack size does *not* at all grow, linearly or otherwise, with the input size, and instead stays constant, like for your `iter` which just juggles data in its two arguments. ---- in Racket, stack lives on the heap, so there's not much difference between iterative and *linear* recursive processes. ---- in r5rs Scheme you can use `set-cdr!`-ing with head sentinel as seen e.g. [here](https://stackoverflow.com/a/13256555/a-tail-recursion-version-list-appending-function) and [elsewhere](https://stackoverflow.com/search?q=set-cdr%21+head+sentinel+%5Bscheme%5D) – Will Ness Sep 10 '20 at 14:19
  • @WillNess Yes, tailcall implies *constant* stack growth. I actually knew this and what I wrote really was a brain fart. Thanks for clarifying. One question: regardless of where the stack lives, the growth rate of an iterative and a linear process are still present? So, when you say that there is no difference between iterative and recursive in Racket, what does that mean exactly? I mean, every recursive call on memory is necessary to resolve the final returned value in a recursive process, while this is not the case with an iterative process. – Snusifer Sep 10 '20 at 16:46
  • I wasn't precise enough. the iterative process exhibits constant stack space usage, but what is its total memory usage? some, like summing the list, also take constant space overall; others, like e.g. copying the list, take linear memory to manipulate the data. in *such* cases, there's no real difference if we just code it as a *linear recursive* process -- it'll take about the same amount of memory, it will just be on the stack instead of on the heap. and in Racket there's no danger of stack overflow any more than using up the whole of available memory anyway, because stack is on the heap. – Will Ness Sep 10 '20 at 17:57

3 Answers3

1

Notice that your iter procedure is almost exactly how reverse is implemented in the first place - no, it's not a recursive process as you mention in the question.

In Racket is simple to check the definition of a procedure: in an edit window without definitions type reverse, right-click it and then select "jump to definition". It'll have a bit of extra code for optimization and error handling, but the core of the algorithm is in the letrec-values part, and it's identical to your iter procedure. So, if we already have that:

(define (reverse ls)
  (let iter ((cp-ls '()) (rest-ls ls))
    (if (null? rest-ls)
        cp-ls
        (iter (cons (car rest-ls) cp-ls) (cdr rest-ls)))))

Then, copy-list is just:

(define (copy-list ls)
  (reverse (reverse ls)))

That's not terribly useful, by the way - if you're not mutating the list, there's no point in copying it. And the reverse of a reverse is just the original thing, isn't it? In fact any implementation of copy-list that operates on immutable lists, for all intents and purposes is equivalent to the identity procedure:

(define (copy-list ls) ls)
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • Well, I wasn't really concerned with the usefulness of this particular procedure, but rather with the idea of keeping a procedure strictly iterative in terms of stack size growth. I thought `reverse` compromised this. But if it is as you say; that `reverse` is in fact an iterative process, then its really not a problem. Thanks for the wisdom! – Snusifer Sep 10 '20 at 16:40
  • By the way, one thing I forgot to ask you. How are you sure of the `reverse` implementation? Anyway to see how Racket has implemented this procedure (r5rs)? – Snusifer Sep 10 '20 at 17:13
  • @Snusifer in Racket is simple: in a window without definitions type `reverse`, right-click it and then select "jump to definition". It'll have a bit of extra code for error handling, but the core of the algorithm is in the `letrec-values` part, and it's identical to your `iter` procedure. – Óscar López Sep 10 '20 at 17:21
1

You can use continuation passing style, return, below -

(define (copy-list ls)
  (let loop ((ls ls) (return identity))
    (if (null? ls)
        (return null)
        (loop (cdr ls)
              (lambda (r) (return (cons (car ls) r)))))))

(copy-list '(1 2 3 4))
; '(1 2 3 4)

Here's what the process looks like -

(copy-list '(1 2 3 4))
(loop '(1 2 3 4) identity)
(loop '(2 3 4) (lambda (r) (identity (cons 1 r))))
(loop '(3 4) (lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))))
(loop '(4) (lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))))
(loop '() (lambda (r) ((lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))) (cons 4 r))))
((lambda (r) ((lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))) (cons 4 r))) null)
((lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))) '(4))
((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) '(3 4))
((lambda (r) (identity (cons 1 r))) '(2 3 4))
(identity '(1 2 3 4))
'(1 2 3 4)
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Mulan
  • 129,518
  • 31
  • 228
  • 259
  • I don't think it should be much slower, in asymptotic terms both are *~ 2n*. the lambdas are not retraced on the inside, are unraveled from the outside in, so it just another *~ n* traversal. even if we say each unraveling (i.e. application) takes time (besides the `cons` itself taking time), then it's *~ 3n* at the most. :) – Will Ness Sep 11 '20 at 06:14
  • Theoretically it should have _n_-runtime, but i've timed it a couple times before and remember it being a lot slower. I would imagine it has something to do with the runtime cost of allocating/evaluating the lambdas. Or maybe there's other optimisations, eg [tail-recursion modulo cons](https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons)?. I'm not familiar enough with the scheme implementation details to know where they "fast" or "slow". – Mulan Sep 11 '20 at 16:12
  • Hmm, I just re-ran a benchmark on list of 10,000 elements and there's not really much of a difference. In fact the double-`reverse` is slower by a smidge! Thanks for sharing Will <3 – Mulan Sep 11 '20 at 16:21
  • 1
    you're welcome. while you're here, maybe also fix the parens and make it `lambda (r)` in the lambdas? btw the way you wrote it might give an unintended impression that each of the lambdas is evaluated in full (and then it _would_ be quadratic). [here's](https://pastebin.com/ey0eMUe5) another way to write it which is clearly linear. (unfortunately it's not fully valid Scheme...) – Will Ness Sep 11 '20 at 16:39
1
(map (lambda(x) x) l)

will make a copy of the list l and it's not recursivelly written.

(let ((l '(1 2 3 4)))
  ((fold-right (lambda (e acc)
                 (lambda (x) (cons x (acc e))))
               (lambda (x) (list x))
               (cdr l))
   (car l)))

is another form to copy a list without recursion, but using a monoid.

other:

(let ((l '(1 2 3 4)))
  (car ((fold-right (lambda (e acc)
                      (lambda (x) (acc (append x (list e)))))
                    (lambda (x) (list x))
                    (cdr l))
        (list (car l)))))

other:

(let ((l '(1 2 3 4)))
  (cdr ((fold-left (lambda (acc e)
                     (lambda (x) (cons x (acc e))))
                   (lambda (x) (list x))
                   l)
        'first)))

other (suggested by Will):

(let ((l '(1 2 3 4)))
  ((fold-right (lambda (e acc)
                 (lambda (k) (k (acc (lambda (es) (cons e es))))))
               (lambda (z) (z (list))) l)
   (lambda (es) es)))

There are lots of other ways to copy a list. In general, to make a copy, you need to call, either directly or indirectly, cons.

As mentioned in the comments, not all these ways use an iterative process.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
alinsoar
  • 15,386
  • 4
  • 57
  • 74
  • This is not correct. `fold-right` is a _recursive_ process (unlike `fold-left`, which is an _iterative_ process), so you're not meeting the requirement in the question. – Óscar López Sep 11 '20 at 09:19
  • 1
    very interesting, thanks. you can do the `'first` and the `cdr` trick with the first `fold-right` snippet as well. I started from it and got `(let ((l '(1 2 3 4))) ((fold-right (lambda (e acc) (lambda (x) (x (acc (lambda (ys) (cons e ys)))))) (lambda (x) (x (list))) l) (lambda (x) x)))` – Will Ness Sep 11 '20 at 18:26
  • 1
    it uses the equivalence `((cons-to xs) x) == ((call-with xs) {cons x})` where `{cons x} = (/\ xs . (cons x xs))` and `((call-with xs) x) = (x xs)`. – Will Ness Sep 11 '20 at 18:35
  • @WillNess I had studied a bit of Haskell in the past, but not enough to master monads. Can you recommend me a way to learn it, such that to develop the intuitions ? I would like to understand how to include monads in the kernel of languages... I programmed with monads in scheme, but not deep enough... – alinsoar Sep 14 '20 at 10:35
  • I can offer some slogans, like "Monads are EDSL", "Monads are first class programs", "Monads are type-encoded reified computations", "Monads are Functors, first", "Monads are generalized nested loops", "Monads are generalized function application", etc.. see https://stackoverflow.com/questions/44965/what-is-a-monad#comment91336013_44965 https://stackoverflow.com/tags/monads/info https://wiki.haskell.org/Monad https://stackoverflow.com/q/11234632/849891 , also some monad related links on my profile page on SO here, or some of my monad answers. – Will Ness Sep 14 '20 at 13:54
  • e.g. https://stackoverflow.com/search?q=user%3A849891+%22The+essence+of+Monad%22, https://stackoverflow.com/search?q=user%3A849891+%22essentially+monadic%22... search for words, skip the Haskellish noise. (also, "Monads are trains that lay their own tracks") – Will Ness Sep 14 '20 at 13:54
  • functors are `for each x in xs: yield (foo x)`. applicative functors are `for each x in xs and y in ys: yield (bar x y)`. monads are: `for each x in xs: for each y in (baz x): yield (baz x y)`. seems like nothing special, really. ---- the meaning of "for", "in", "yield" is determined by the type of values involved. so it's a value, like list of Ints, that will be interpreted as a nondeterministic computation (as one example). `for each x in [1,2,3]: yield (repeat 2 x)` produces `[[1,1], [2,2], [3,3]]`, so is of wrong type - a computation producing computations. so it needs to be `join`ed. – Will Ness Sep 14 '20 at 14:04
  • i.e. `concat`ed (or `apply append`ed). thus splicing those lists in place. monads are functors with `join`. – Will Ness Sep 14 '20 at 14:09
  • @WillNess Waw. You are very kind for such an elaborate answer :). Thank you! – alinsoar Sep 14 '20 at 14:46
  • you're welcome. correcting a typo: `monads are: for each x in xs: for each y in (baz x): yield (bar x y)`. so if an overall value of type `m a` stands for a computation of `a`-type results, and we transform each inner result `a` to an `m b` type value, we've produced `m (m b)` - a computation description that will produce... computation descriptions. and we just want to treat the overall computation description as describing a computation of results, not of computation descriptions... math people are sticklers for details. or in Haskell, `join :: m (m b) -> m b`. – Will Ness Sep 14 '20 at 14:56
  • [see also](https://stackoverflow.com/questions/44117197/why-does-haskells-bind-function-take-a-function-from-non-monadic-to-monadic/44118041#44118041) – Will Ness Sep 14 '20 at 15:03
  • @WillNess I am also a math guy. I saw lots of times the statement "type m a stands for a computation" but I do not understand it too much. It is like returning a function that will lazily be called afterwards. Could you recommend me also, apart from online topics, some paper that is written from scratch and it's also deep in the same time (some SICP of Haskell...) ? – alinsoar Sep 14 '20 at 15:06
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/221463/discussion-between-will-ness-and-alinsoar). – Will Ness Sep 14 '20 at 15:06