Попытка получить схему глубины-первого или пята-первого поиска Функция Currying для работы

Question

Я здесь новый, и мне нужна помощь с функцией, которую я пишу в схеме.

В основном, это функция поиска, которая может работать как для поиска по ширине, так и для поиска по глубине. Я думаю, что я начал работать с Depth-First-Merge и Breadth-First Merge.

Однако проблема заключается в том, чтобы изменить основной поиск для работы как функцию «currying», так что когда алгоритмы слияния с конкретным алгоритмом (такие как слияние по глубине или слияние по ширине) передаются в в качестве аргументов поиск использует этот тип поиска. Возврат

Есть два файла, которые у меня есть. Монеты в порядке, но поиск требует исправления. Как изменить функцию поиска здесь, чтобы работать как карри?

Вот мои коды ниже. первый для поиска. Я сделал поиск2 как раннюю попытку, но это не сработало. Мне нужно сделать поиск или поиск2 работать как карри-поиск (затем удалить другой). Я не уверен, но я думаю, что слияния и два поиска работают.

;;; 
;;; SEARCH: 
;;; -- Non-curried version of generic search algorithm 
;;; -- Can be customized for depth-first and breadth-first search 
;;; -- You must convert it to a curried version so that 
;;;  - the function accepts 1 algorithm specific parameter and returns a function 
;;;  - that accepts 3 problem-specific parameters and returns a function 
;;;  - that accepths 1 instance specific parameter and performs the search 
;;; -- The 5 parameters are described below 
;;; 
;;; Input: 
;;; merge-queue 
;;;  -- algorithm specific 
;;;  -- procedure that takes a list of new paths and a queue 
;;;  and returns a new queue 
;;; extend 
;;;  -- problem-specific 
;;;  -- procedure that takes a state and a list of visited states, 
;;;  and returns a list of states that are reachable in one move 
;;;  from the given state 
;;; goal? 
;;;  -- problem-specific 
;;;  -- predicate that takes a state and returns true if the 
;;;  state is a goal state, false otherwise 
;;; print-path 
;;;  -- problem-specific 
;;;  -- procedure that takes a state and prints out a state nicely 
;;; init-state 
;;;  -- problem instance-specific 
;;;  -- an initial state to start the search from 
;;; 
;;; OUTPUT: 
;;; -- When succeeded, a path from the initial state to a goal state 
;;; -- When failed, #f 
;;; 


;;Either this or search2 needs to be rewritten into a curried version 
;;To accept either depth-first-merge or breadth-first merge as merge procedures into merge-queue 
(define search 
    (lambda (merge-queue init-config extend goal? print-state) 
    (letrec 
     ((helper 
    (lambda (queue) 
    (newline) 
    (for-each 
    (lambda (p) (print-path p print-state)) 
    queue) 
     (cond ((null? queue) #f) 
      ((goal? (caar queue)) 
     (print-state (caar queue)) 
     (newline) 
     (let ((ans (reverse (car queue)))) 
     (for-each (lambda (x) (print-state x) (newline)) ans) 
     ans)) 
      (else 
       (let ((successors (extend (caar queue)))) 
     (print-state (caar queue)) (newline) 
       (cond ((null? successors) 
         (helper (cdr queue))) 
         (else 
      (for-each (lambda (x) (print-state x) (newline)) 
       successors) 
      (helper 
      (merge-queue (cdr queue) 
       (extend-path successors (car queue)))))))))))) 
    (helper 
    (list (list (config->state init-config)))))) 



(define search2 
    (lambda (merge-queue extend goal? print-path init-state) 
(letrec 
    ((search-helper 
     (lambda (queue visited) 
     (cond 
      ((null? queue) #f) 
      ((goal? (caar queue)) 
      (begin 
       (print-path (car queue)) 
       (car queue))) 
      (else 
      (let ((successors (extend (caar queue) visited))) 
       (cond 
       ((null? successors) 
        (search-helper (cdr queue) visited)) 
       (else 
        (let ((new-paths (extend-path successors (car queue)))) 
        (search-helper 
      (merge-queue queue new-paths) 
      (cond 
      (merge-queue)) 
         (append successors visited))))))))))) 
    (search-helper 
    (list (list init-state)) ; initial queue 
    (list init-state)))))  ; initial visited 


(define extend-path 
    (lambda (successors path) 
    (if (null? successors) 
    '() 
    (cons (cons (car successors) path) 
     (extend-path (cdr successors) path))))) 



;; merge new extended paths to queue for depth first search 
;; - uncomment and define your merge for depth first search 

(define depth-first-merge 
    (lambda (queue paths) 
    (append! paths queue))) 

;; merge new extended paths to queue for breadth first search 
;; - uncomment and define your merge for breadth first search 

(define breadth-first-merge 
    (lambda (queue paths) 
    (append! queue paths))) 


;; customize the generic search for depth first search 
;; - uncomment and define your depth-first-search in terms of your 
;; curried version of search and depth-first-merge 
;; Curry Methods are helpful to this. 

(define depth-first-search (search depth-first-merge)) 
    (lambda (extend goal? print-path) 
    (search (depth-first-merge extend goal? print-path)))) 



;; customize the generic search for breadth first search 
;; - uncomment and define your breadth-first-search in terms of your 
;; curried version of search and breadth-first-merge 

(define breadth-first-search (search breadth-first-merge)) 
    (lambda (extend goal? print-path) 
    (search (breadth-first-merge extend goal? print-path)))) 

И это код файла монет, который используется для дополнения кода поиска. Они находятся в отдельных файлах и загружают search.ss (выше) для работы.

;; load algorithm specific code for search 
(load "search.ss") 

;;; Problem specific code for solving the old British coin problems 
;;; using the curried version of the simple search procedure. 
;;; The old British coin problem was discussed in the lecture. 
;;; 
;;; To solve the problem, load this file and run 
;;; (coin-depth-first amount) 
;;; or 
;;; (coin-breadth-first amount) 
;;; where, amount is replaced with some number, e.g., 48. 
;;; 
;;; Here, a state is represented as follows: 
;;;  (amount (coin1 coin2 ...)) 
;;; 
;;; The car of the state represents how much change you need to pay further. 
;;; The cadr of the state represents the combination of coins you used 
;;; to pay so far. For example, 
;;;  (48()) 
;;; is the initial state for the amount of 48 cents and 
;;;  (0 (24 24) 
;;; can be one of the goal states using two 24-cent coins. 


;; There are 7 kinds of old British coins 
(define old-british-coins '(120 30 24 12 6 3 1)) 

;; Or, you can do the same for US coins 
(define us-coins '(100 50 25 10 5 1)) 

;; Here, we will do the old British coins 
(define *coins* old-british-coins) 


;; Is a state the goal state? 
(define goal? 
    (lambda (state) 
    (zero? (car state)))) 


;; returns children of a state 
(define extend 
    (lambda (state visited) 
    (let ((coins (applicable-coins state visited *coins*))) 
    (map 
    (lambda (coin) 
     (list (- (car state) coin) 
     (append (cadr state) (list coin)))) 
    coins)))) 


;; find all applicable coins from a state 
(define applicable-coins 
    (lambda (state visited coins) 
    (cond 
    ((null? coins) '()) 
    ((<= (car coins) (car state)) 
     (if (visited? state visited (car coins)) 
     (applicable-coins state visited (cdr coins)) 
     (cons (car coins) (applicable-coins state visited (cdr coins))))) 
    (else (applicable-coins state visited (cdr coins)))))) 


;; see if a state has been visited before 
(define visited? 
    (lambda (state visited coin) 
    (cond 
    ((null? visited) #f) 
    ((= (- (car state) coin) (caar visited)) #t) 
    (else (visited? state (cdr visited) coin))))) 


;; pretty-print a state 
(define pretty-print-path 
    (lambda (path) 
    (pretty-print-state (car path)))) 

(define pretty-print-state 
    (lambda (state) 
    (let ((change (car state)) 
     (coins (cadr state)) 
     (total (apply + (cadr state)))) 
    (printf 
    "===> Total of ~a paid with ~a, with remainder of ~a <===~%" 
    total coins change)))) 


;; customize the generic depth-first-search for coin problem 
(define coin-depth-first-search 
    (depth-first-search extend goal? pretty-print-path)) 

;; instance of a coin problem using depth-first search 
(define coin-depth-first 
    (lambda (amount) 
    (coin-depth-first-search (list amount '())))) 



;; customize the generic breadth-first-search for coin problem 
(define coin-breadth-first-search 
    (breadth-first-search extend goal? pretty-print-path)) 


;; instance of a coin problem with breadth-first search 
(define coin-breadth-first 
    (lambda (amount) 
    (coin-breadth-first-search (list amount '())))) 

Может кто-нибудь, пожалуйста, помогите мне? Я думаю, что все, что мне нужно, чтобы заставить его работать, это выяснить, как сделать код поиска или search2 превращенным в карри.

Answer 1

Керри функции означает переопределить ее таким образом, чтобы она принимала несколько параметров меньше текущего определения и возвращает новую функцию, которая принимает остальные параметры и выполняет работу первого , Например, вы можете снискать следующие две параметры функции суммирования:

(define add 
    (lambda (a b) 
    (+ a b))) 

(add 7 10) ;; => 17 

следующим образом:

(define add-to 
    (lambda (a) 
    (lambda (b) 
     (+ a b)))) 

((add-to 7) 10) ;; => 17 

(define add-to-7 (add-to 7)) ;; we give a name to the function that add 7 to its argument 

(add-to-7 8) ;; => 15 

(add-to-7 9) ;; => 16 

Таким образом, чтобы преобразовать функцию search2 (вы должны расширить эту функцию с момента его последнего параметра это экземпляр проблема специфична):

(define search2 
    (lambda (merge-queue extend goal? print-path init-state) 
    ...body of search2... 

по мере необходимости, можно было бы просто написать что-то вроде этого:

(define search2 
    (lambda (merge-queue) 
    (lambda (extend goal? print-path) 
     (lambda (init-state) 
     ...body of search2... 

и затем, называя его правильным количеством параметров, вы можете получить «частичные» функции, которые будут вызываться позже.Например, вы можете определить общую глубину первого поиска как:

(define depth-first-search (search2 depth-first-merge)) 

, то вы можете определить глубину первого поиска специализированный для этой проблемы монеты, даны соответствующие определения для функций монет:

(define coin-depth-first (depth-first-search coin-extend coin-goal? coin-print-path)) 

и, наконец, вы можете назвать это с определенным количеством, чтобы решить эту проблему:

(coin-depth-first 100)