On Thu, 2010-01-07 at 00:37 -0800, CK Kashyap wrote:
Hi All,
I've written this piece of code to do permutations -
I assume that it's training piece not real code as in such I'd recommend:
import Data.List perms = permutations
perms :: String -> [String] perms []= []
As pointed out perms [] = [[]]. You can note that: length . perms == factorial
perms (x:[])= [[x]] perms (x:xs)= concat (f [x] (perms xs))
Don't call function f. I'd look into parameters - i.e. map f xs is = ... ok as f is some user function but f xs does not say what f is (except it is some function ;) ). Also pointed out concatMap:
perms (x:xs) = concatMap spread
spread :: String -> String -> [String] -- interpolate first string at various positions of second string spread str1 str2 = _spread str1 str2 (length str2)
I'd always be careful with (!!) and length. Both have O(n) complexity and I've seen code in which it shifted from O(n^3) to O(n^6) by uncareful usage (usually something like O(n) to O(n^2) per function).
where _spread str1 str2 0= [str1 ++ str2] _spread str1 str2 n= [(take n str2) ++ str1 ++ (drop n str2)] ++ (_spread str1 str2 (n-1))
Please note that the first list (here list of chars) have always length 1. It would be nice to indicate it by rewriting into:
spread :: a -> [a] -> [[a]] spread a b = _spread a b 0 where _spread a b 0 = [a:b] _spread a b n = ((take n b) ++ a:(drop n b)):(_spread a b (n-1)) perms (x:xs) = concatMap (spread x) (perms xs)
I took the liberty of rewriting [a] ++ b into a:b. In fact (:) is base constructor as the list [1,2,3,4] is syntax sugar for 1:2:3:4:[]. Hence it should be marginally more effective w/out optimalizations Further clarification is
spread a b = map (\n -> (take n b) ++ a:(drop n b)) Or: spread a b = zipWith (\i e -> i ++ a:e) (inits b) (tails b)
(\n -> something) is lambda function and is shorthand of ... f ... where f n = something
f xs = map (spread xs)
Why make separate function (not in where)
The number of outcomes seem to indicate that correctness of the algo .. however, I'd be very obliged if I could get some feedback on the Haskellness etc of this ... also any performance pointers ...
Minor difficulty with algorithm - it diverges for:
head $ head $ perms [1..]
Regards, Kashyap
Regards