1

I've been attempting to refactor my original solution to a getPermutations() function using a point-free approach using Ramda.js. Is it possible to refactor it further, towards a point-free style. It looks like I just made an even bigger mess. Also, there is currently a bug in the refactored version when I run the tests: TypeError: reduce: list must be array or iterable.

Original Solution:

// getPermutations :: String -> [String]
function getPermutations(string) {
  function permute(combination, permutations, s) {
    if (!s.length) {
      return permutations[combination] = true;
    }

    for (var i = 0; i < s.length; i++) {
      permute( combination.concat(s[i])
             , permutations
             , (s.slice(0, i) + s.slice(i+1))
             );
    }
    return Object.keys(permutations);
  }

  return permute('', {}, string);
}

My attempt to refactor with Ramda.js:

var _ = require('ramda');

// permute :: String -> {String: Boolean} -> String -> [String]
var permute = _.curry(function (combination, permutations, string) {
  // callPermute :: String -> ({String: Bool} -> Char -> Int -> String) -> IO
  var callPermute = function (combination) {
    return function (acc, item, i, s) {
      return permute( _.concat(combination, item)
                    , acc
                    , _.concat(_.slice(0, i, s), _.slice(i + Infinity, s))
                    );
    };
  };

  var storeCombination = function () { 
    return permutations[combination] = true;
  };

  // should be an ifElse, incorporating compose below
  _.when(_.not(string.length), storeCombination);

  return _.compose( _.keys
                  , _.addIndex(_.reduce(callPermute(''), {}))
                  ) (string.split(''));
});

// getPermutations :: String -> [String]
var getPermutations = permute('', {});
Eric
  • 31
  • 1
  • 6
  • What's your question? Do you just want to write the `permute` function in point-free style? That's very difficult. – Aadit M Shah May 18 '16 at 03:29
  • @AaditMShah, that is correct. I was hoping to write the `permute` function in a point-free style. Your feedback helps. I wasn't sure if I was missing something simple, looking at the problem incorrectly/sub-optimally, or if recursive functions are inherently difficult to refactor into point-free style. Thanks for the feedback! – Eric May 18 '16 at 06:53
  • I agree that it's often not worth refactoring to points-free, especially difficult to achieve points-free recursion without resorting to a fixed-point combinator. But I don't agree that this questions should be closed as a duplicate of the linked question which was not about points-free, did not mention a library, did not talk about refactoring existing code, and, in fact, only shared with this one that they both wanted a permutation function in JS. That does not make them duplicates. – Scott Sauyet May 19 '16 at 01:04

1 Answers1

0

There seem to be several problems with your solution, and I'm afraid I don't have time to chase them down. (The first thing I see is that you are using addIndex incorrectly.)

But if you want to see a working permutation function in Ramda, I wrote this a while ago:

// permutations :: [a] -> [[a]]
const permutations = (tokens, subperms = [[]]) =>
  R.isEmpty(tokens) ?
    subperms :
    R.addIndex(R.chain)((token, idx) => permutations(
      R.remove(idx, 1, tokens), 
      R.map(R.append(token), subperms)
    ), tokens);

R.map(R.join(''), permutations(['A', 'B', 'C'])); 
//=> ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

(You can play with this on the Ramda REPL.)

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103
  • Your solution is not point-free, if that's what the OP wanted. – Aadit M Shah May 18 '16 at 03:30
  • @ScottSauyet, Thanks for the tip about `addIndex`. I was really confused about why that wasn't working. And even though it's not point free, I'm really digging your solution. It sounds like I may have been attempting a ridiculous exercise in trying to make it point-free. I know my refactor wasn't even close, but I wanted to show my attempt at least before asking for help. Are most recursive functions inherently difficult to write in a point-free style, or just some? – Eric May 18 '16 at 07:11
  • @Eric Every function can be converted into a point-free version. However, that doesn't mean that every function should. Point-free functions make sense in very limited cases like [eta conversion](https://en.wikipedia.org/wiki/Lambda_calculus#.CE.B7-conversion) or [function composition](https://en.wikipedia.org/wiki/Function_composition). In most other cases, pointful functions are more readable. There's an [algorithm](https://en.wikipedia.org/wiki/Combinatory_logic#Completeness_of_the_S-K_basis) to convert pointful expressions into point-free expressions. – Aadit M Shah May 18 '16 at 09:21