I want to split a string into a list of strings of given length using fold.
split :: n -> String -> [String]
split 4 "abcdefghijklmnopqrst" -> ["abcd","efgh","ijkl","mnop","qrst"]
Can this be done using foldr? Can you provide an explanation so I could gain some intuition on how to use folds to solve problems like this?
Edit: I have added the recursive solution
split :: Int -> String -> [String]
split len xs
| len >= length xs = [xs]
| otherwise = take len xs : split len (drop len xs)
To go from your recursive code to foldr you need to further inline and fuse the definitions of length, take and drop so that your code deconstructs the input list one element at a time, like foldr does:
split :: Int -> [a] -> [[a]]
split len xs
| len >= length xs = [xs]
| otherwise = take len xs : split len (drop len xs)
where
take :: Int -> [a] -> [a]
take 0 xs = xs
take 0 [] = []
take n (x:xs) = x : take (n-1) xs
-- and for `drop` and `len >= length` as well
-- ......
So we need to add a counter for that.
split2 :: Int -> [a] -> [[a]]
split2 len xs = go xs 0
where
go [] _ = [[]] -- [] : []
go (x:xs) i
| i < len = [x] : go xs (i+1)
| otherwise = go xs 0
(do fix the off-by-one error(s) here, would you).
This of course doesn't produce the right results but it already follows the foldr pattern! It does the counting and the skipping along all at once, and correctly chooses the point to restart counting from 0 which corresponds to the recursive call with the dropped list -- already done for free, all by just going along the input list one element at a time -- like foldr does. We just need to save those elements we currently forget:
split3 :: Int -> [a] -> [[a]]
split3 len xs = go xs 0 []
where
go [] _ ys = [reverse ys]
go (x:xs) i ys
| i < len = go xs (i+1) (x:ys)
| otherwise = reverse (x:ys) : go xs 0 []
This directly maps onto the foldr recursion pattern, where we replace go (x:xs) on the LHS with g x r and go xs on the RHS with r:
split4 :: Int -> [a] -> [[a]]
split4 len xs = foldr g z xs 0 []
where
z _ ys = [reverse ys]
g x r i ys
| i < len = r (i+1) (x:ys)
| otherwise = reverse (x:ys) : r 0 []
-- > split4 4 "123456"
-- ["12345","6"]
Again, do fix the off-by-one error, please.
This isn't fully lazy, though, i.e. (!! 0) . head . split4 3 $ "12"++undefined will diverge instead of returning the character '1' as it arguably should.
To achieve that, we must return the structure right away, even if with holes in it, and fill those holes later:
split5 :: Int -> [a] -> [[a]]
split5 len xs = foldr g z xs 1
where
z _ = [[]]
g x r i
| i < len = let (a:b) = r (i+1) in (x:a):b
| otherwise = [x] : r 1
With this,
> split5 4 "123456"
["1234","56"]
> take 2 . head . split5 4 $ "12" ++ undefined
"12"
Still there's a corner case here where the return value isn't quite right. Do find it, and try to fix it, too.
As others commented, using fold is probably not the best approach here. Nevertheless it is an interesting exercise.
From the signature of foldr we can figure out that the accumulator needs to be of type [String] and the combine operator of type Char -> [String] -> [String].
To implement combine, notice that we can append character by character to the accumulator. In the process we need to take care to start with a new string every time we exceed n characters:
split :: Int -> String -> [String]
split n = foldr combine []
where
combine c (x:xs) | length x < n = (c:x):xs
combine c xs = [c]:xs
