Option type encoding / robustness in Lisp

Question

(define (nth n lst)
  (if (= n 1)
    (car lst)
    (nth (- n 1)
         (cdr lst) )))

is an unsafe partial function, n may go out of range. An error can be helpful,

(define (nth n lst)
  (if (null? lst)
    (error "`nth` out of range")
    (if (= n 1)
      (car lst)
      (nth (- n 1)
           (cdr lst) ))))

But what would a robust Scheme analogue to Haskell's Maybe data type look like?

data Maybe a = Nothing | Just a

nth :: Int -> [a] -> Maybe a
nth _ []       = Nothing
nth 1 (x : _)  = Just x
nth n (_ : xs) = nth (n - 1) xs

Is just returning '() adequate?

(define (nth n lst)
  (if (null? lst) '()
    (if (= n 1)
      (car lst)
      (nth (- n 1)
           (cdr lst) ))))

Answer 1

There are several ways to do this.

The direct equivalent would be to mimic the Miranda version:

#!r6rs
(library (sylwester maybe) 
  (export maybe nothing maybe? nothing?)
  (import (rnrs base))

  ;; private tag 
  (define tag-maybe (list 'maybe)) 

  ;; exported tag and features
  (define nothing (list 'nothing))

  (define (maybe? v)
    (and (pair? v) 
         (eq? tag-maybe (car v))))

  (define (nothing? v)
    (and (maybe? v)
         (eq? nothing (cdr v))))

  (define (maybe v)
    (cons tag-maybe v)))

How to use it:

#!r6rs
(import (rnrs) (sylwester maybe))
(define (nth n lst)
  (cond ((null? lst) (maybe nothing))
        ((zero? n) (maybe (car lst)))
        (else (nth (- n 1) (cdr lst)))))

(nothing? (nth 2 '()))
; ==> #t

Exceptions

(define (nth n lst)
  (cond ((null? lst) (raise 'nth-nothing))
        ((zero? n) (car lst))
        (else (nth (- n 1) (cdr lst)))))


(guard (ex
        ((eq? ex 'nth-nothing)
         "nothing-value"))
  (nth 1 '())) ; ==> "nothing-value"

Default value:

(define (nth n lst nothing)
  (cond ((null? lst) nothing)
            ((zero? n) (car lst))
            (else (nth (- n 1) (cdr lst)))))

(nth 1 '() '()) 
; ==> '()

Deault value derived from procedure

(define (nth index lst pnothing)
  (cond ((null? lst) (pnothing))
        ((zero? n) (car lst))
        (else (nth (- n 1) (cdr lst)))))

(nth 1 '() (lambda _ "list too short")) 
; ==> "list too short"

Combination of exception and default procedure

Racket, a Scheme decent, often has a default value option that defaults to an exception or a procedure thunk. It's possible to mimic that behavior:

(define (handle signal rest)
  (if (and (not (null? rest))
           (procedure? (car rest)))
      ((car rest))
      (raise signal)))

(define (nth n lst . nothing)
  (cond ((null? lst) (handle 'nth-nothing nothing)) 
        ((zero? n) (car lst))
        (else (nth (- n 1) (cdr lst)))))

(nth 1 '() (lambda () 5)) ; ==> 5
(nth 1 '()) ; exception signalled

Answer 2

As a non-lisper I really can't say how idiomatic this is, but you could return the Church encoding of an option type:

(define (nth n ls)
  (cond
    ((null? ls) (lambda (default f) default))
    ((= n 1) (lambda (default f) (f (car ls))))
    (else (nth (- n 1) ls))))

But that's about as complicated to use as @Dirk's proposal. I'd personally prefer to just add a default argument to nth itself.

Answer 3

Another way to signal, that no matching element was found, would be to use multiple return values:

(define (nth n ls)
  (cond
    ((null? ls) (values #f #f))
    ((= n 1) (values (car ls) #t))
    (else (nth (- n 1) ls))))

This comes at the expense of being a little bit cumbersome for the users of this function, since they now have to do a

(call-with-values (lambda () (nth some-n some-list))
                  (lambda (element found?)
                     ... whatever ...))

but that can be alleviated by using some careful macrology. R7RS specifies the let-values syntax.

(let-values (((element found?) (nth some-n some-list)))
   ... whatever ...)

Answer 4

It's easy to break your attempt. Just create a list that contains an empty list:

(define lst '((1 2) () (3 4)))
(nth 2 lst)
-> ()
(nth 100 lst)
-> ()

The key point that you're missing is that Haskell's Maybe doesn't simply return a bare value when it exists, it wraps that value. As you said, Haskell defines Maybe like so:

data Maybe a = Nothing | Just a

NOT like this:

data Maybe a = Nothing | a

The latter is the equivalent of what you're doing.

To get most of the way to a proper Maybe, you can return an empty list if the element does not exist, as you were, but also wrap the return value in another list if the element does exist:

(define (nth n lst)
  (if (null? lst) '()
    (if (= n 1)
      (list (car lst)) ; This is the element, wrap it before returning.
      (nth (- n 1)
           (cdr lst) ))))

This way, your result will be either an empty list, meaning the element did not exist, or a list with only one element: the element you asked for. Reusing that same list from above, we can distinguish between the empty list and a non-existant element:

(define lst '((1 2) () (3 4)))
(nth 2 lst)
-> (())
(nth 100 lst)
-> ()