Okay, major help needed if someone out there has the time, this has been killing my brain for ages.
-- e.g., insertions 'c' "ab" = ["cab", "acb", "abc"]
-- It may help to define two functions which call each other.
Thus far I have.
insertions :: x -> [x] -> [[x]]
insertions x [] = [[]]
insertions x (y:ys) = ??
Name:
Anonymous2009-06-23 21:32
'C' + "AB" = ABCAB
Think about it:
ABCAB ABCAB ABCBA
ABC BCA CBA
Name:
Anonymous2009-06-23 21:38
So, you want to insert 'c' into 'ab' at all possible positions, and return a list of those?
import Data.List (splitAt)
insertions :: a -> [a] -> [[a]]
insertions _ [] = []
insertions a as =
let asrep = replicate (length as + 1) as
zipped = zip [0..] asrep
insert (n, l) = let (f, s) = splitAt n l in f ++ [a] ++ s
inserted = map insert zipped
in inserted
Name:
Anonymous2009-06-23 21:53
insertions c = uncurry (zipWith $ flip (++).(c:)).(tails &&& inits)
Name:
Anonymous2009-06-23 22:04
insertions :: x -> [x] -> [[x]]
insertions x [] = [[x]]
insertions x (y:ys) = (x:y:ys):map (y:) (insertions x ys)
Name:
Anonymous2009-06-23 22:05
>>5
Pardon me. insertions :: x -> [x] -> [[x]]
insertions x [] = [[x]]
insertions x (y:ys) = (x:y:ys):map (y:) (insertions x ys)
insertions :: a -> [a] -> [[a]]
insertions _ [] = []
insertions a as =
map (\(n, l) -> let (f, s) = splitAt n l in f ++ [a] ++ s) $
zip [0..] $ replicate (length as + 1) as
naiveInsertions :: x -> [x] -> [[x]]
naiveInsertions x [] = [[x]]
naiveInsertions x (y:ys) = (x:y:ys):map (y:) (insertions x ys)
test :: String -> [[a]] -> IO ()
test name list = do
start <- getCurrentTime
let !eval = sum (map length list)
end <- getCurrentTime
let diff = diffUTCTime end start
putStrLn $ name ++ ": took " ++ show diff ++ " seconds"
main = do
let list = [1..20000]
let f = insertions 1 list
let fa = arrowInsertions 1 list
let fn = naiveInsertions 1 list
test "mine" f
test "arrows" fa
test "naive" fn
$ ghc --make insertions -O3
[1 of 1] Compiling Main ( insertions.hs, insertions.o )
Linking insertions ...
$ ./insertions
mine: took 28.078299s seconds
arrows: took 84.96184s seconds
naive: took 26.349743s seconds
$
Name:
Anonymous2009-06-24 1:20
holy shit brainwashhed haskell fags do homework for you on /prog/.
What the hell happened to "DONT HELP HIM!!"
>>13
Sepples uses float and/or double instead of real.
Name:
Anonymous2009-06-24 17:11
>>16
Interesting piece of trivia:
see/sepples use double by default; one must explicitely use the `f' suffix on a floating-point literal if they want 32-bit floats.