[plt-scheme] How to fold it

Yeap, that's the proper way of thinking about it:

#lang scheme

(require test-engine/scheme-tests)

;; slide : [Listof X] -> [Listof [Listof X]]
;; create all prefixes of a-list

(check-expect (slide '(0 1 2 3 4)) '((0) (0 1) (0 1 2) (0 1 2 3) (0 1  
2 3 4)))

(define (slide.v0 a-list)
   (cond
     [(empty? a-list) empty]
     [else (cons (list (first a-list))
                 (map (lambda (x) (cons (first a-list) x))
                      (slide (rest a-list))))]))

(define (slide a-list)
   (foldr (lambda (ft rt) (cons (list ft) (map (curry cons ft) rt)))  
'() a-list))

(test)

-- Matthias



On May 16, 2009, at 4:32 AM, R. Emre Başar wrote:

> The general approach I follow in these kind of cases is an idea I got
> from the Design Recipe:
>
> 1- The value you produce in the empty case is the empty case of foldr.
> 2- The function you pass to foldr (let's call it f) is the else  
> part of
> your condition, wrapped inside a lambda with two parameters.
> 3- All the (first a-list)'s in your code is the first parameter of f.
> 4- The result of the recursion is the second parameter of f.
>
> Do the substitutions and your foldr'd program is ready.
>
> I think it is possible to convert any program that is a simple
> structural recursion on one value to a foldr using this methodology. I
> guess somebody already proved it somewhere.
>
> Jordan Johnson der ki:
>> This feels clunky to me, but how about:
>>
>> (define (slide ls)
>>   (reverse (foldl (lambda (x ls)
>>                     ;; e.g.: 2 '((0 1) (0)) ==> ((0 1 2) (0 1) (0))
>>                     (if (null? ls)
>>                       (list (list x))
>>                       (cons (append (car ls) (list x))
>>                             ls)))
>>                   '()
>>                   ls)))
>>
>> I also tried it as an unfold, which was cute by comparison, at the  
>> cost
>> of some reversing:
>>
>> (require srfi/1)
>>
>> (define (slide2 ls)
>>   (unfold-right null?
>>                 reverse
>>                 rest
>>                 (reverse ls)))
>>
>> Cheers,
>> jmj
>>
>> On May 15, 2009, at 8:04 PM, wooks wrote:
>>
>>> ;;slide :: [*] -> [[*]]
>>> ;;Given a list like '(0 1 2 3 4) produces '((0) (0 1) (0 1 2) (0 1 2
>>> 3) (01 2 3 4))
>>> (define slide
>>>   (lambda (a-list)
>>>     (cond
>>>       [(empty? a-list) empty]
>>>       [else (cons (list (first a-list))
>>>                   (map (lambda (x) (cons (first a-list) x))
>>>                        (slide (rest a-list))))])))
>>>
>>> This code is in the spirit of HTDP 12.4.2. The map prefixes the
>>> inductive case with the first of the list and
>>>
>>>         cons (list (first a-list))
>>>
>>> was what was required to get from what I had to what I wanted.
>>>
>>> It looks like something that should be foldable. How to get there?
>>>
>>> _________________________________________________
>>>   For list-related administrative tasks:
>>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> -- 
> R. Emre Başar
> İstanbul Bilgi University
> Department of Computer Science
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme