;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname lect39-append3-prolog) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
; append3 : list, list, list -> boolean
; Does appending `l1` to `l2` yield the list `result`?
(define (append3 l1 l2 result)
  (cond [(and (empty? l1) (empty? l2))
         (empty? result)]
        [(and (empty? l1) (cons? l2))
         (equal? l2 result)]
        [(and (cons? l1) (empty? l2))
         (equal? l1 result)]
        [(and (cons? l1) (cons? l2))
         (and (equal? (first l1) (first result))
              (append3 (rest l1) l2 (rest result)))]
        ))

#|
append3(L1,L2,Result) :- L1=[], L2=[], Result=[].
append3(L1,L2,Result) :- L1=[], L2=[F|R], L2=Result.
append3(L1,L2,Result) :- L1=[F|R], L2=[], L1=Result.
append3(L1,L2,Result) :- L1=[F1|R1], L2=[F2|R2], Result=[FR|RR], F1=FR, append3(R1,L2,RR).

% now, simplify:

%append3([],[],[]).  % this rule is subsumed by the next rule (and the next).
append3([],L2,L2).
append3(L1,[],L1).
append3([F|R],L2,[F|RR]) :- append3(R,L2,RR).
|#


; Alternately / optional [not discussed]:
; take this code/version, and translate it:
; It uses the insight that we can think about `append` w/o
; ever needing to "look inside" l2.
;
(define (append2 l1 l2)
  (cond [(empty? l1) l2]
        [(empty? l2) l1]
        [else (cons (first l1)
                    (append2 (rest l1) l2))]))





(check-expect (append3 '() '() '())  #t)
(check-expect (append3 '() '() '(1))  #f)
(check-expect (append3 '() '(1) '(1))  #t)
(check-expect (append3 '() '(1) '())  #f)
(check-expect (append3 '(1) '(2) '(1 2)) #t)
(check-expect (append3 '(1 2 3) '(4 5 6) '(1 2 3 4 5 6)) #t)
(check-expect (append3 '() '() '(1 2))  #f)
(check-expect (append3 '(a b) '() '(a b)) #t)
(check-expect (append3 '(a b) '() '()) #f)