CODEWITHSUNDEEP
functional-programmingscheme
yrazlik
yrazlik

Reputation: 10777

How to determine whether an input is a sequence in scheme?

I am new to functional programming and trying to write a function that takes a list parameter and returns true if the list consists of symbols where each symbol is of length 1. More specifically, 

;(sequence? '(a b c)) ----> true
; (sequence? '(aa b c)) ---> false since aa has length 2
; (sequence? '(a 1 c)) ----> false since 1 is not a symbol
; (sequence? '(a (b c))) --> false since (b c) is not a symbol

I am thinking about doing the following: For each symbol in the list, i check whether it is a symbol and it is of length 1. 

(define sequence?
      (lambda (inSeq)
      (if ( for each item in the list inSeq, all are symbols and length=1) #t #f)

      )
)

Then according to result i return true or false. But i do not know how to iterate over the list. I do not want to convert the list into a string and use string functions. Do we have any statements like "foreach", or for loop to do what i think? or any other suggestions?

Note: I also thought about using car and then removing it and looking at the rest of the list, but since i do not know the length, i do not know how many times should i use the car, i.e. whether it should be car, caar, caaar, etc.

Thank you

Upvotes: 1

Views: 484

Answers (4)

GoZoner
GoZoner

Reputation: 70145

If you've solved the problem for the first element of the list, then you've solved it for the remainder of the elements of the list just by reapplying the same procedure to the rest.

For the first element you need the following:

(define (is-symbol-1 thing)
  (and (symbol? thing)
       (= 1 (string-length (symbol->string thing))))

and then

(define (sequence? list)
  (or (null? list)                     ;; #t if list is empty
      (and (is-symbol-1 (car list))    ;; first element is-symbol-1
           (sequence?   (cdr list))))) ;; and rest is sequence? too

This is an example of recursion. As you learn Scheme, you'll benefit by looking for opportunities to exploit recursion.

Upvotes: 2

Óscar López
Óscar López

Reputation: 236004

A simple way, using readily available functions - in particular, you could use andmap in Racket (or for-all in R6RS, or every in SRFI-1); think of it as a foreach that returns #t if all the elements in a list satisfy a predicate. This solution is more in line with the spirit of functional programming, in the sense that it uses generic, higher-order procedures to solve a new problem by combining existing solutions to other subproblems. In other words, we don't reinvent the wheel:

(define (sequence? seq)      ; `seq` is a sequence if
  (andmap (lambda (e)        ; it's true for all its elements that
            (and (symbol? e) ; each element is a symbol
                 (= 1 (string-length (symbol->string e))))) ; with length one
          seq))

Notice how the code says exactly what it means: a list is a "sequence" if it's true, for all of its elements, that each one is a symbol of length one. To determine a symbol's length, we convert it first into a string, which we can easily check to see if it meets the length requirement. It works as expected:

(sequence? '(a b c))
=> #t
(sequence? '(aa b c))
=> #f
(sequence? '(a 1 c))
=> #f
(sequence? '(a (b c)))
=> #f

Upvotes: 2

Alan Gilbert
Alan Gilbert

Reputation: 365

First, let's figure out a lambda that will return true when its argument is a symbol of length one, and false otherwise:

(λ (x) (and (symbol? x) (= (string-length (symbol->string x)) 1)))

;; 'a -> #t, 'aa -> #f, '(a) -> #f

We had to use a string function there, because there is no meaningful difference between the symbol 'f and the symbol 'foo, except in their string representation.

Now, let's take that lambda and use it to filter bad elements from our list:

(filter (λ (x) (and (symbol? x) (= (string-length (symbol->string x)) 1))) 
        '(a b c))

;; '(a b c) -> '(a b c), '(a 2 c) -> '(a c), '(a bb c) -> '(a c)

Now, let's check to make sure that nothing was filtered out, i.e. every element of our original list was a symbol of length 1. We do that by checking that the length of our output list is the same as the length of our input list.

(define (symbols-of-length-1 seq)
  (= (length (filter (λ (x) (and (symbol? x) (= (string-length (symbol->string x)) 1))) 
             seq))
     (length seq)))

;; '(a b c) -> #t, '(a 2 c) -> #f, '(a (b) c) -> #f, '(a bb c) -> #f

Upvotes: 2

sepp2k
sepp2k

Reputation: 370132

Do we have any statements like "foreach", or for loop to do what i think?

No.

or any other suggestions?

To iterate over a list in scheme, you'd either use pre-existing functions that iterate over the list (like map, filter or fold-left) or you write your own using recursion. Depending on which Scheme dialect you're using, there might already be a function (called every or andmap) that takes a list and a condition and returns #t iff the condition is true for every item in the list. Otherwise, you'd have to write it recursively or as a fold (though not all Scheme dialects have fold function either).

A recursive function that iterates over a list usually looks something like this:

(define (do-something-with-list lst)
  (if (null? lst)
    (handle-the-case-that-list-is-empty)
    (combine
      (some-transformation-on (car lst))
      (do-something-with-list (cdr lst)))))

For example to sum all numbers in a list that are greater than 5 (without using filter or fold-left), you'd write:

(define (sum-all-numbers>5 numbers)
  (if (null? numbers)
    ; Sum of the empty list is 0
    0 
    (+
      ; If the head of the list is > 5, add the number to the result, else
      ; add 0
      (if (> (car numbers) 5) (car numbers) 0)
      (sum-all-numbers>5 (cdr numbers)))))

You can use the same approach to define your function.

PS: (if condition #t #f) is redundant -- you can just write condition (unless condition is something other than a boolean and you need to convert it to a boolean, but I can't think of a scenario where that'd be necessary).

Upvotes: 2

Related Questions