[Top] [All Lists]

[Haskell-cafe] Re: Review request for my permutations implementation

 Subject: [Haskell-cafe] Re: Review request for my permutations implementation Maciej Piechotka Thu, 07 Jan 2010 14:04:20 +0100
 ```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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe ```
 Current Thread [Haskell-cafe] Review request for my permutations implementation, CK Kashyap Re: [Haskell-cafe] Review request for my permutations implementation, Jochem Berndsen Re: [Haskell-cafe] Review request for my permutations implementation, Daniel Fischer Re: [Haskell-cafe] Review request for my permutations implementation, Rafael Gustavo da Cunha Pereira Pinto Re: [Haskell-cafe] Review request for my permutations implementation, CK Kashyap [Haskell-cafe] Re: Review request for my permutations implementation, Maciej Piechotka <= Re: [Haskell-cafe] Re: Review request for my permutations implementation, Daniel Fischer [Haskell-cafe] Re: Re: Review request for my permutations implementation, Maciej Piechotka