[Haskell-cafe] Review request for my permutations implementation

[Jochem Berndsen]

CK Kashyap wrote:
> I've written this piece of code to do permutations -

First off, this is a recurring topic. If you search the archives, you'll
find some more topics about it.

> perms :: String -> [String]

Why this type? Since a String is just a list of Char, and you don't use
the fact that you're actually using a list of characters. It's better to
keep this function generic, and say

  perms :: [a] -> [[a]]

> perms []= []

I don't think this is what you expect or want. I would consider a
permutation of X to be a bijection X -> X. The number of bijections X ->
X when X is empty, is in fact 1. So I think

  perms [] = [[]]

> perms (x:[])= [[x]]

I think you can drop this case if you do perms [] = [[]]. (Didn't prove
it, though.)

> perms (x:xs)= concat (f [x] (perms xs))

A small stylistic issue: Normally I'd write a space before the '='.

> spread :: String -> String -> [String] -- interpolate first string at various positions of second string

This function becomes easier if you define it like

  spread :: a -> [a] -> [[a]]

since you only use it in that way.

> spread str1 str2 = _spread str1 str2 (length str2)
> where
> _spread str1 str2 0= [str1 ++ str2]
> _spread str1 str2 n= [(take n str2) ++ str1 ++ (drop n str2)] ++ (_spread str1 str2 (n-1))
> 
> f xs = map (spread xs)

There is a better way to write spread, something like

  spread str1 xs = zipWith (\x y -> x ++ str1 ++ y)
                           (inits xs)
                           (tails xs)

with inits and tails from Data.List.


HTH, regards, Jochem
-- 
Jochem Berndsen | jochem at functor.nl | jochem@牛在田里.com