Higher-Order String Functions

January 26, 2016

Scheme provides the higher-order functions map, for-each and fold that operate on lists. In today’s exercise we will write versions of those functions that operate on strings:

(string-map proc str) applies proc to each character in str, replacing the character with the output of proc. proc takes a single character and returns a single character.

(string-for-each proc str) applies proc to each character in str; the function is executed only for its side-effects. proc takes a single character and returns nothing.

(string-fold proc base str) calls function (proc base c) on each character of str, working left to right, accumulating the result in base as it goes. proc takes a base of any type, and a character, and returns a value of the same type as base. (string-fold-right proc base str) is the same, except that it works from right to left.

Your task is to implement these four functions in the language of your choice. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 Responses to “Higher-Order String Functions”

  1. fisherro said
    #include <algorithm>
    #include <cctype>
    #include <iostream>
    #include <iterator>
    #include <numeric>
    #include <sstream>
    #include <string>
    
    //#define USE_STD_ALGO 1
    //#define RANGED_FOR_BACKWARDS 1
    
    std::string string_map(char (*proc)(char), const std::string& input)
    {
        std::string output;
    #ifdef USE_STD_ALGO
        //The standard C++ map function, transform, can operate directly on strings.
        std::transform(input.begin(), input.end(), std::back_inserter(output),
                proc);
    #else
        //The new ranged-for syntax is less verbose.
        for (auto c: input) output.push_back(proc(c));
    #endif
        return output;
    }
    
    template<typename Proc>
    void string_for_each(Proc proc, std::string& input)
    {
    #ifdef USE_STD_ALGO
        //The standard C++ for_each function works directly on strings.
        std::for_each(input.begin(), input.end(), proc);
    #else
        //Again, however, the ranged-for syntax is less verbose.
        for (auto& c: input) proc(c);
    #endif
        //With STL2 ranges, the std::for_each version will become:
        //  std::for_each(input, proc);
        //So, ranged-for will lose the concision advantage.
    }
    
    template<typename Proc, typename Base>
    Base string_fold(Proc proc, Base base, const std::string& input)
    {
    #ifdef USE_STD_ALGO
        //The standard C++ fold function, accumulate, works directly on strings.
        base = std::accumulate(input.begin(), input.end(), base, proc);
    #else
        //Again, the ranged-for is less verbose.
        for (auto c: input) base = proc(base, c);
    #endif
        return base;
    }
    
    template<typename Proc, typename Base>
    Base string_fold_right(Proc proc, Base base, const std::string& input)
    {
    #ifdef USE_STD_ALGO
        //With the standard algorithms, iterating backwards is as easy as using
        //rbegin and rend in place of begin and end.
        base = std::accumulate(input.rbegin(), input.rend(), base, proc);
    #elif !defined(RANGED_FOR_BACKWARDS)
        //Another limitation of ranged-for: No easy way to iterate backwards.
        //So, we do it the old-fashioned way.
        for (auto i = input.rbegin(); i != input.rend(); ++i)
            base = proc(base, *i);
    #else
        //Or, we can use a helper struct to get ranged-for to work.
        struct {
            const std::string& input;
            auto begin() { return input.rbegin(); }
            auto end() { return input.rend(); }
        } helper = { input };
        for (auto c: helper) base = proc(base, c);
    #endif
        return base;
    }
    
    char rot13(char c)
    {
        //C++ gives you very few guarantees about char.
        //It may be signed or unsigned.
        //Letters might not be continguous.
        //I know my platform uses ASCII (or UTF-8) and a signed char.
        //So this is platform specific code.
        unsigned char uc = c;
        if (std::isalpha(uc)) {
            unsigned char z = std::isupper(uc)? 'Z': 'z';
            uc += 13;
            if (uc > z) uc -= 26;
        }
        return uc;
    }
    
    int main()
    {
        {
            //To test string_map, we use it to rot13 a string.
            std::string input("Hello, world!");
            std::string output = string_map(rot13, input);
    #ifndef NDEBUG
            std::cout << input << " -> " << output << '\n';
    #endif
            std::cout << "string_map test: " <<
                ((output == "Uryyb, jbeyq!")? "PASSED": "FAILED") << '\n';
        }
    
        {
            //To test string_for_each, we pass it a closure that simply accumulates
            //the characters via a string stream. We expect the output of the
            //string stream to match the input.
            std::string input("Hello, world!");
            std::ostringstream oss;
            string_for_each([&oss](char c){ oss << c; }, input);
    #ifndef NDEBUG
            std::cout << input << " -> " << oss.str() << '\n';
    #endif
            std::cout << "string_for_each test: " <<
                ((input == oss.str())? "PASSED": "FAILED") << '\n';
        }
    
        {
            //To test string_fold, we use integer addition for the procedure, zero
            //for the base, and "2<" for the string. We expect 110 as a result.
            //'2' == 50; '<' == 60; '2' + '<' = 110.
            //This depends on char being ASCII (or UTF-8).
            std::string input("<2");
            int sum = string_fold(std::plus<int>(), 0, input);
    #ifndef NDEBUG
            std::cout << sum << '\n';
    #endif
            std::cout << "string_fold test: " <<
                ((110 == sum)? "PASSED": "FAILED") << '\n';
        }
    
        {
            //To test string_fold_right, in the proc we append the character to the
            //base. The resulting string should be the reverse of the input.
            std::string input("Hello, world!");
            std::string output = string_fold_right(
                    [](std::string base, char c) { return base + c; },
                    std::string(), input);
    #ifndef NDEBUG
            std::cout << output << '\n';
    #endif
            std::cout << "string_fold_right test: " <<
                ((output == "!dlrow ,olleH")? "PASSED": "FAILED") << '\n';
        }
    }
    
  2. fisherro said

    My scheme version. I probably should’ve used make-string.

    #lang r5rs
    
    ;;; The simplest way (though perhaps not efficient) to implement these
    ;;; functions is to convert the string to a list and use the list functions.
    
    ;(define (string-map proc str)
    ;  (list->string (map proc (string->list str))))
    ;
    ;(define (string-for-each proc str)
    ;  (for-each proc (string->list str)))
    ;
    ;(define (string-fold proc base str)
    ;  (fold-left proc base (string->list str)))
    ;
    ;(define (string-fold-right proc base str)
    ;  (fold-right proc base (string->list str)))
    
    ;;; But we'll use the string functions to implement them instead...
    
    ;; Implement fold first, since it can be used for map and for-each.
    (define (string-fold proc base str)
      (let ((len (string-length str)))
        (let loop ((accumulator base)
    	       (i 0))
          (if (< i len)
    	(loop (proc accumulator (string-ref str i))
    	      (+ i 1))
    	accumulator))))
    
    (define (string-fold-right proc base str)
      (let ((len (string-length str)))
        (let loop ((accumulator base)
    	       (i (- len 1)))
          (if (>= i 0)
    	(loop (proc accumulator (string-ref str i))
    	      (- i 1))
    	accumulator))))
    
    (define (string-map proc str)
      (string-fold (lambda (accumulator character)
    		 (string-append accumulator (string (proc character))))
    	       ""
    	       str))
    
    (define (string-for-each proc str)
      (string-fold (lambda (accumulator character)
    		 (proc character))
    	       #f
    	       str))
    
    ;; A rot13 function for test below.
    (define (rot13 character)
      (if (char-alphabetic? character)
        (let ((i (+ 13 (char->integer character)))
    	  (z (char->integer (if (char-upper-case? character)
    			      #\Z
    			      #\z))))
          (integer->char
    	(if (> i z)
    	  (- i 26)
    	  i)))
        character))
    
    ;;; Tests!
    ;;; Since string-map and string-for-each use string-fold,
    ;;; we don't test string-fold directly.
    
    (display (string-map rot13 "Hello, world!"))
    (newline)
    
    (string-for-each display "Hello, world!")
    (newline)
    
    (display (string-fold-right
    	   (lambda (accumulator character)
    	     (string-append accumulator (string character)))
    	   ""
    	   "Hello, world!"))
    (newline)
    
  3. Informatimago said

    Well this is one useless exercise in Common Lisp: in Common Lisp, strings are vectors, and vectors are sequences, so all the vectors and the sequence operations apply to strings. map, map-into, reduce, reverse, length, equal, etc… So the solution of this problem in CL, is null, apart perhaps from the renaming (which is dumb, and caused the problem in scheme in the first place; use generic functions!):

    (defun string-map (proc str) (map 'string proc str))
    (defun string-for-each (proc str) (map nil proc str))
    (defun string-fold (proc base str) (reduce proc str :initial-value base))
    (defun string-fold-right (proc base str) (reduce proc str :initial-value base :from-end t))
    

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: