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('', {});
3
  • What's your question? Do you just want to write the permute function in point-free style? That's very difficult. Commented May 18, 2016 at 3: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! Commented May 18, 2016 at 6: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. Commented May 19, 2016 at 1:04

1 Answer 1

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

Sign up to request clarification or add additional context in comments.

3 Comments

Your solution is not point-free, if that's what the OP wanted.
@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 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 or function composition. In most other cases, pointful functions are more readable. There's an algorithm to convert pointful expressions into point-free expressions.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.