I have been working on a function that return a FSM that searches a specific word based on the argument of the constructor. The idea was to use those routines as means to learn about regular expressions and maybe implement a very basic regexp system, so I thought that matching normal string was a good first step in that direction.
This is actually my first "complex" program in Scheme. I learnt to program in C so it has been a little hard to switch my way of thinking into a functional approach, so any comments in my way of programming in Scheme would also be very useful.
I know that using lists might not be the most efficient thing to do, but they allowed me to program in a more functional way without using
If there is something to add or to fix please don't just put the answer, that way I won't learn. Try to use code only if necessary.
Sadly Emacs uses tabs for indentation so formatting may be a little messy.
An automata in my code is represented as a list of states where each one is described as a pair of the form (a . b) where a is the matched character and b is the index of the state it transitions to. If no pair contains a specific character then it defaults to the invalid state (index = 0).
run-automata function searches a matching substring and returns its offset or
#f if it is not contained inside
(define (string-null? s) (= (string-length s) 0)) (define (string-append-c s c) (string-append s (string c))) (define (string-tail str) (substring str 1 (string-length str))) ;; is s2 a prefix of s1? ;; [TODO] - Use offset instead of string-tail (define (string-prefix? s1 s2) (cond [(string-null? s2) #t] [(string-null? s1) #f] [(not (char=? (string-ref s2 0) (string-ref s1 0))) #f] [else (string-prefix? (string-tail s1) (string-tail s2))])) (define (enumerate start end) (define (iter start end acc) (if (> start end) acc (iter start (- end 1) (cons end acc)))) (iter start end '())) (define (build-automata needle) (define (max-suffix-that-is-prefix str) (cond [(string-null? str) ""] [(not (string-prefix? needle str)) (max-suffix-that-is-prefix (string-tail str))] [else str])) (define (build-transitions state-string transitions dictionary) (if (null? dictionary) transitions (let* ([c (car dictionary)] [suffix (max-suffix-that-is-prefix (string-append-c state-string c))]) (build-transitions state-string (if (string-null? suffix) transitions (cons (cons c (string-length suffix)) transitions)) (cdr dictionary))))) ;; Last state does not require a transition as it is the final state. ;; "We are done by that point". (let ([dictionary (string->list "abcdefghijkmnopqrstuvwxyz")]) (map (lambda (n) (build-transitions (substring needle 0 n) '() dictionary)) (enumerate 0 (- (string-length needle) 1))))) ;; Takes an automata and a string and returns the offset of the pattern the ;; automata was built to search (define (run-automata automata string) (define (search-transition c state-transitions) (cond [(null? state-transitions) 0] [(char=? (caar state-transitions) c) (cdar state-transitions)] [else (search-transition c (cdr state-transitions))])) (define (step state automata-size offset) (cond [(= state automata-size) (- offset automata-size)] [(>= offset (string-length string)) #f] [else (step (search-transition (string-ref string offset) (list-ref automata state)) automata-size (+ offset 1))])) (step 0 (length automata) 0))