Idiomatic functional way to move disc in Towers of Hanoi

I am learning Scheme and as a toy example I am doing a solution verifier (not a solver) for Towers of Hanoi. I want to use a purely functional style (just to get into the mindset) and I represent the tower as a simple list of three lists. The starting state can look something like this: '((0 1 2 3 4) () ())

How would I implement a function that takes a state, a source index and a target index and returns the new state? In an imperative style this would be something trivial like:

state[target].push(state[source].pop())

But every functional solution I can think of is terribly convolu开发者_运维百科ted. For example:

(define (makeMove state source target)
  (letrec ((recMake (lambda(tower pos disc)
              (if (null? tower) '()
              (cons (if (eqv? pos source)
                    (cdr (car tower))
                    (if (eqv? pos target) 
                    (cons disc (car tower))
                    (car tower)))
                (recMake (cdr tower)
                     (+ pos 1)
                     disc))))))
    (recMake state 0 (car (list-ref state source)))))

This seems to work, but there must be a better way. I suppose a map would be somewhat better than recursion, but still too much. Would it be easier if I represented state differently?

Also, feel free to criticize my code. I don't really know what I am doing.

EDIT: If possible, I prefer that you not assume that the number of towers are always 3.

Here's a super-straightforward way. I'm not sure what the significance of the disc "numbers" are in your implementation, but I made it behave the same as your answer does, pushing and popping them.

(define (make-move state source target)
  (define (alter-tower tower index disc)
    (cond ((= index source) (cdr tower))       ; remove a disc
          ((= index target) (cons disc tower)) ; add a disc
          (else tower)))                       ; this tower wasn't changed
  (let ((disc (car (list-ref state source))))
    (let ((s0 (alter-tower (list-ref state 0) 0 disc))
          (s1 (alter-tower (list-ref state 1) 1 disc))
          (s2 (alter-tower (list-ref state 2) 2 disc)))
      (list s0 s1 s2))))

If you assume the existence of a map-with-index function, which comes standard in many languages and libraries but is not built into Scheme, then you could roll up the bottom set of operations on each tower into a call to that, and it would be much cleaner.

In general, try to come up with pure functions down to the lowest level possible which do what you want. In this solution, I invented a pure function "alter-tower" which can return the result of your command on a single tower, and that's what makes the rest of the solution very straightforward.

Since you asked for feedback, I note that = is identical for eqv? when applied to numbers, that internal defines work in Scheme and act as you'd expect (e.g. you can call them recursively) and that the usual naming convention in Lisp is to separate multi-word identifiers with hyphens, instead of using camel-case. Good luck!

EDIT: Here's a version, for example, that uses Racket's list comprehensions:

(define (make-move state source target)
  (define (alter-tower tower index disc)
    (cond ((= index source) (cdr tower))       ; remove a disc
          ((= index target) (cons disc tower)) ; add a disc
          (else tower)))                       ; this tower wasn't changed
  (let ((disc (car (list-ref state source))))
    (for/list ([(tower idx) (in-indexed state)])
      (alter-tower tower idx disc))))

Many functional languages have a map that can take a predicate which consumes the index, so those two lines might instead look like:

(map (lambda (tower idx) (alter-tower tower idx disc)) state)

So depending on your Scheme dialect and libraries it might be different. (I don't think there's an SRFI for this, but I might be mistaken.) Or you could always write the above version of map yourself.