Hi All, I've spent a lot of time trying to write a version of concat, which concatenates lists of any "depth": So: concat'' [[[1,2],[3,4]],[[5]]] would return: [1,2,3,4,5] The code is: concat'' :: [a] -> [b] concat'' ((y:ys):xs) = (concat'' (y:ys)) ++ (concat'' xs) concat'' [] = [] concat'' (x:xs) = (x:xs) And the inevitable error is: test.hs:298:12: Couldn't match expected type `a' against inferred type `[t]' `a' is a rigid type variable bound by the type signature for `concat''' at test.hs:297:13 In the pattern: y : ys In the pattern: (y : ys) : xs In the definition of `concat''': concat'' ((y : ys) : xs) = (concat'' (y : ys)) ++ (concat'' xs) test.hs:300:24: Couldn't match expected type `b' against inferred type `[t]' `b' is a rigid type variable bound by the type signature for `concat''' at test.hs:297:20 In the first argument of `(:)', namely `x' In the expression: (x : xs) In the definition of `concat''': concat'' (x : xs) = (x : xs) Failed, modules loaded: none. Any help or advice would be appreciated. Will
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 12/29/10 22:05 , william murphy wrote:
I've spent a lot of time trying to write a version of concat, which concatenates lists of any "depth": So: concat'' [[[1,2],[3,4]],[[5]]] would return: [1,2,3,4,5]
You can't do that, at least with a normal type signature. There might be some evil that can do it, but (as you found) if you try to do it naively you will get an error which amounts to "this type can't represent both an item and a list of that item at the same time". - -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk0b+Z0ACgkQIn7hlCsL25WFCQCeNkSf0+1pyJI+rpBWtk3uBsv5 qosAoIRQQyg78IPlHuQiiVleqmYUdQD+ =lOjO -----END PGP SIGNATURE-----
First, what type would such a function have? Certainly not [a]->[b], because that type say that it can take a list of any type and turn it into a list of any other type, e.g., [Int]->[Bool]. On Thu, Dec 30, 2010 at 4:05 AM, william murphy <will.t.murphy@gmail.com>wrote:
Hi All,
I've spent a lot of time trying to write a version of concat, which concatenates lists of any "depth": So: concat'' [[[1,2],[3,4]],[[5]]] would return: [1,2,3,4,5]
The code is: concat'' :: [a] -> [b] concat'' ((y:ys):xs) = (concat'' (y:ys)) ++ (concat'' xs) concat'' [] = [] concat'' (x:xs) = (x:xs)
And the inevitable error is: test.hs:298:12: Couldn't match expected type `a' against inferred type `[t]' `a' is a rigid type variable bound by the type signature for `concat''' at test.hs:297:13 In the pattern: y : ys In the pattern: (y : ys) : xs In the definition of `concat''': concat'' ((y : ys) : xs) = (concat'' (y : ys)) ++ (concat'' xs)
test.hs:300:24: Couldn't match expected type `b' against inferred type `[t]' `b' is a rigid type variable bound by the type signature for `concat''' at test.hs:297:20 In the first argument of `(:)', namely `x' In the expression: (x : xs) In the definition of `concat''': concat'' (x : xs) = (x : xs) Failed, modules loaded: none.
Any help or advice would be appreciated. Will
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Wed, 29 Dec 2010, william murphy wrote:
Hi All,
I've spent a lot of time trying to write a version of concat, which concatenates lists of any "depth": So: concat'' [[[1,2],[3,4]],[[5]]] would return: [1,2,3,4,5]
You can nicely solve this problem in Haskell 98 using a Tree data structure. Data.Tree might help and also has a 'flatten' function.
participants (4)
-
Brandon S Allbery KF8NH -
Henning Thielemann -
Lennart Augustsson -
william murphy