Return a sublist of a given list only using lambda and built-in higher-order list functions

2
votes

I have a problem with writing a function (sublist list from to) which consumes two parameters, from and to, and produces the subsequence from the list that begins at the index from and ends before the index of to, where indexing starts at 0. For instance,

 (sublist '(a b c d e f g h) 1 4) ==> '(b c d)
 (sublist '(a b c d e f g h) 1 1) ==> '()
 (sublist '(a b c d) 0 30) ==> '(a b c d)

I understand that if we are allowed to use local helper functions, we can write a helper function that counts up from 0 and proceed from there.

However, if we are not allowed to use local, is it possible to only use built-in higher-order list functions and lambda functions to solve this problem? Greatly appreciated!

3
lambdaschemerackethigher-order-functions
what is "abstract list functions", did you mean "higher-order functions" perhaps, or is "built-in functions"...? – Will Ness
I suspect that you've become stuck by assuming that you need a counter. – molbdnilo
For abstract list functions, I mean filter, foldr, foldl, build-list and map. I think it means built-in list functions. – Emily W
May I know how can I do it without the counter? Thanks! – Emily W
there were / are no counters per se in the answers, only argument indices manipulation, but I've since edited with two HOF-based variants if that's what you meant. :) One of them still does the indices manipulation, the other does it differently. – Will Ness

3 Answers

1
votes

Anything you can do with a helper function you can do by recursion in the main function, by re-purposing its argument(s).

For instance, your sublist expects integer numbers as its 2nd and 3rd parameter; you could put anything there (usually a tagged list, like (list 'sublist_internal_invocation n1 n2 ...)) and have your function react to that fact, knowing that it is it itself that put it there, i.e. it is used as its own helper that way.

That is, if there is a need for it. In your case, there probably isn't, i.e. it can just be written as a plain recursive function, by augmenting the list and / or the indices at each recursive call.

To give you a hint,

     (sublist '(a b c d e f g h) 1 4)

is the same as

       (sublist '(b c d e f g h) 0 3)

and that is the same as

(cons 'b (sublist '(c d e f g h) 0 2))

Right?

Thus (sublist '(d e f g h) 0 1) is (cons 'd (sublist '(e f g h) 0 0)) and hence (sublist '(e f g h) 0 0) must be '().

update: if for some reason direct recursion is not what you want, the above fits into the foldr paradigm so indeed can be translated into it; though with a twist. foldr is defined so that

(foldr g z (cons x xs))  ==  (g x (foldr g z xs))   ; AND
(foldr g z (list))  ==  z

Thus we see that to fit the above examples g must be defined so that

((g x (foldr g z xs)) i j)  ==  
   ==  (cons x ((foldr g z xs) i (- j 1)))  , WHEN i == 0, j > i   ; OR
   ==  ((foldr g z xs) (- i 1) (- j 1))     , WHEN i > 0, j > i    ; OR
   ==  (list)                               , OTHERWISE            ; AND

((foldr g z (list)) i j)
   ==  (z i j)
   ==  (list)

The third case in the first clause accounts also for the possibility that the indices supplied by a user were invalid; and the second clause determines the definition of z.

Now what's left is just to write all this down with the regular lambda syntax:

(define (sublist xs i j)
  ((foldr 
     (lambda (x ys) 
       (lambda (i j)
         (cond 
           ((and (= i 0) (> j i))
             (cons x (ys i (- j 1))))
           ((and ...... )
                     ............)
           (else
             (list)))))
      (lambda (i j)
             ......)
      xs)  i  j ))

A simpler possibility is

(define (sublist xs i j)
  (map .....
    (filter
      (lambda (xk)
         (and (>= (cadr xk) .....) (..... (cadr xk) .....)))
      (map list
           xs
           (build-list (....... xs) (lambda (x) x))))))

You will need to complete the missing parts, on the dots.

0
votes

Yes, it is possible to do this, and the key is thinking about what from and to mean:

  • if from is more than zero, it means we're not at the start of the interesting bit of the list yet, so we want to simply try again on the tail of the list, but with from & to one less than they currently are;
  • if to is zero then we're at the end of the interesting bit of the list and want to return '() immediately;
  • otherwise we're actively collecting elements, so arrange to collect the first element combined with collecting the elements from the tail of the list, again with from and to being one less than their current values (you don't actually need to bother with subtracting anything from from).

Note there are no sanity checks in this code: in real life you'd want to do an initial check that from and to are sane.

0
votes

Using map filter second range list lambda < -

(define (sublist lst from to)
  (map second (filter (lambda (p) (< (- from 1) (car p) to))
                      (map list (range (length lst)) lst))))
  1. Pair each element of lst with its index number. (map list (range (length lst)) lst).
  2. filter for pairs (< (- from 1) index-number to). (filter <condition-fulfiller> <index-paired lst>).
  3. Using (map second ...) remove the index-numbers again.

Tail call recursive solution

(define (sublist lst from to (acc '()))
  (cond ((or (empty? lst) (zero? to)) (reverse acc))
        ((zero? from) (sublist (cdr lst) 0 (- to 1) (cons (car lst) acc)))
        (else (sublist (cdr lst) (- from 1) (- to 1) acc))))

Collect current first element of lst and forward the in-between results in acc whenever from is zero but lst is neither empty nor to is not zero yet. At every step by going from element to element decrease from and to by one exceptfrom is alredy zero, then pass zero for from.