Ordered Vowels

January 31, 2017

A vowel is a letter a, e, i, o, or u:

(define (vowel? c)
  (member c '(#\a #\e #\i #\o #\u #\A #\E #\I #\O #\U)))

We begin with a function that examines each letter in a word to determine if it is a vowel and if it is not less than the previous vowel:

(define (ordered-vowels? str)
  (let loop ((cs (string->list str)) (prev #\space))
    (cond ((null? cs) #t)
          ((not (vowel? (car cs))) (loop (cdr cs) prev))
          ((char<=? prev (car cs)) (loop (cdr cs) (car cs)))
          (else #f))))
> (ordered-vowels? "afoot")
#t

Then we write a program that reads words (one per line) from a file and writes those that pass ordered-vowels?:

(define (ordered-vowel-words filename)
  (with-input-from-file filename
    (lambda ()
      (let loop ((word (read-line)))
        (unless (eof-object? word)
          (when (ordered-vowels? word)
            (display word) (newline))
          (loop (read-line)))))))

The output includes words like a, aardvark, afoot, and zymurgy.

That works, but it’s horrible to have to write those loops. Higher-order functions make things a lot prettier:

(define (ordered-vowels? str)
  (sorted? char<? (filter vowel? (string->list str))))
(define (ordered-vowel-words filename)
  (for-each-input
    (filter-input read-line ordered-vowels?)
    (lambda (word) (display word) (newline))
    filename))

Output is the same as the previous version. For-each-input, filter-input and read-line are in the Standard Prelude; sorted? should be, but isn’t:

(define (sorted? lt? xs)
  (cond ((null? xs) #t)
        ((null? (cdr xs)) #t)
        ((lt? (cadr xs) (car xs)) #f)
        (else (sorted? lt? (cdr xs)))))

You can run the program at http://ideone.com/yRAySq.

Advertisements

Pages: 1 2

5 Responses to “Ordered Vowels”

  1. maximeeuziere said

    Your regex doesn’t seem to handle doubled vowels separated by non-vowels, like, ALBATROS

    so something like that may be more accurate: ‘^([^aeiou]*a)*([^aeiou]*e)*([^aeiou]*i)*([^aeiou]*o)*([^aeiou]u*)*[^aeiou]*$’

    also, in some languages “y” is also a vowel. (not in english?)

  2. Paul said

    In Python.

    from glob import glob
    
    VOWELS = "aeiou"
    WORDLISTFILES = glob('D:/Data/Development/spell/en/english.?')
    WORDLIST = (w.strip().lower() for f in WORDLISTFILES for w in open(f))
    
    def check(word):
        vowels = [c for c in word if c in VOWELS]
        return sorted(vowels) == vowels
    
    print(list(word for word in WORDLIST if check(word)))
    
  3. Jussi Piitulainen said

    A finite-state automaton then, for the Finnish set of vowel characters.

    (define-syntax at
      (syntax-rules ()
        ((at state ((c0 c1 ...) next) ...)
         (define (state rest)
           (or (null? rest)
               (case (car rest)
                 ((c0 c1 ...) (next (cdr rest)))
                 ...
                 (else (state (cdr rest)))))))))
    
    (at a* ((#\e) e*) ((#\i) i*) ((#\o) o*) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at e* ((#\a) no) ((#\i) i*) ((#\o) o*) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at i* ((#\a #\e) no) ((#\o) o*) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at o* ((#\a #\e #\i) no) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at u* ((#\a #\e #\i #\o) no) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at y* ((#\a #\e #\i #\o #\u) no) ((#\ä) ä*) ((#\ö) ö*))
    (at ä* ((#\a #\e #\i #\o #\u #\y) no) ((#\ö) ö*))
    (at ö* ((#\a #\e #\i #\o #\u #\y #\ä) no))
    (define (no rest) #f)
    
    (define (ow<= s) (a* (string->list s)))
    
    ;; Guile stuff
    (use-modules (ice-9 rdelim))
    (set-port-encoding! (current-input-port) "UTF-8")
    (set-port-encoding! (current-output-port) "UTF-8")
    
    (do ((line (read-line) (read-line)))
        ((eof-object? line))
      (if (ow<= (string-downcase line)) (begin (write line) (newline))))
    

    Testing with a 1916 translation of Homer’s Odysseus from Project Gutenberg,
    recall looks about right:

    $ tr -s ' \n\r' '\n' < Documents/pg52108.txt | guile ow.scm | awk 'rand() < .001'
    "taas"
    "yhä"
    "maito."
    "Yö"
    "lahden"
    "hän"
    "vastassani"
    "Kenenkään"
    "ja"
    "ei"
    "eikä"
    "eikö"
    "\"Jalo"
    "ja"
    "\"Tämäpä"
    "mitä"
    "must"
    
  4. Zack said

    An implementation in Julia, from scratch (i.e. no external libraries whatsoever). Using the complete scrabble dictionary (~173K words), it took a little over a second to work out all the words with ascending vowels and store them in a string array. I also added an auxiliary function to retrieve the dictionary words from the text file I’ve put them in. Here is the source code:

    function GetWordsFromDictionary{T <: AbstractString}(fn::T = "D:\\data\\words.txt")
    f = open(fn)
    words = split(readall(f), ",")
    close(f)
    return words
    end

    function ascending(v::Array{Char, 1})
    n = length(v)

    for i = 2:n
    if v[i] < v[i-1]; return false; end
    end

    return true
    end

    function AllVowels{T 0]
    vowels = Array(Char, n)

    for i = 1:n
    vowels[i] = word[ind[i]]
    end

    return vowels
    end

    function vao{T <: AbstractString}(words::Array{T, 1}) # this is the main function
    n = length(words)
    ind = falses(n)

    for i = 1:n
    ind[i] = ascending(AllVowels(words[i]))
    end

    return words[ind]
    end

    Probably not the most elegant solution, but I prefer to keep the code in a modular format so that I can reuse parts of it in other scripts (something quite common in functional languages).

  5. Globules said

    Here’s a Haskell version. You supply an ascending list of vowels as a command-line argument. The function hasOrderedSubsequence works for any type that supports equality, not just characters. I’ve included the output of two runs: one with English vowels (I don’t count ‘y’) on the Mac dictionary, another with Finnish vowels (taken from Jussi’s program) on the same translation of Homer’s Odyssey.

    import Data.Char (toLower)
    import Data.List (elemIndex)
    import Data.List.Ordered (isSorted)
    import Data.Maybe (mapMaybe)
    import System.Environment (getArgs)
    
    -- hasOrderedSubsequence ords xs is True if all elements of xs, that occur in
    -- ords, appear in the same order as in ords.  Otherwise, the value is False.
    hasOrderedSubsequence :: Eq a => [a] -> [a] -> Bool
    hasOrderedSubsequence ords = isSorted . mapMaybe (`elemIndex` ords)
    
    main :: IO ()
    main = do
      let lower = map toLower
      vowels <- concatMap lower <$> getArgs
      interact (unlines . filter (hasOrderedSubsequence vowels . lower) . words)
    
    $ ./ordvowels "aeiou" < /usr/share/dict/words | awk 'rand() < 0.0003'
    anemony
    araban
    bossdom
    brandering
    Canton
    che
    epinicion
    French
    grapelet
    hatmaking
    hough
    lapsing
    miswish
    needments
    racism
    syringitis
    talabon
    toyon
    wrathily
    $ ./ordvowels "aeiouyäö" < ~/Downloads/pg52108.txt | awk 'rand() < 0.001'
    taas
    yhä
    maito.
    Yö
    lahden
    hän
    vastassani
    Kenenkään
    ja
    ei
    eikä
    eikö
    "Jalo
    ja
    "Tämäpä
    mitä
    must
    $ 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: