Programming Praxis

3 Responses to “Higher-Order String Functions”

1. fisherro said

   January 26, 2016 at 11:21 PM

   #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

   January 26, 2016 at 11:25 PM

   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

   January 30, 2016 at 10:35 PM

   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))