CODEWITHSUNDEEP
haskellconstructorconcatenation
Travis Quigg
Travis Quigg

Reputation: 11

Concatenation, Haskell

Hi I am currently trying to concatenate two lists in Haskell similar to this:

l1 = [[aa,adb,adc], [aa,dd,gg]] l2 = [[cc,abd,hh], [hh, cc, vvvv]] result: l3 = [[aa,adb,adc], [aa,dd,gg], [cc,abd,hh], [hh, cc, vvvv]]

here is my Haskell code:

Length-Ordered Lists over "character type" a (aka "strings over a") Invariant: In LOL n xs, n == length xs Note that automatically-derived Ord instance correctly orders LOLs

data LOL a = LOL Int [a] deriving (Eq,Ord)
instance Show a => Show (LOL a) where
show (LOL n xs) = show xs

-- Empty list (epsilon)

eps :: LOL a
eps = LOL 0 []

establish invariant

lol :: [a] -> LOL a
lol xs = LOL (length xs) xs

Normalized lists of LOLS Lang a implies xs is ordered with no duplicates

type Lang a = [LOL a]

establish invariant

lang :: Ord a => [[a]] -> Lang a
lang xs = norm $ map lol xs

Here is where I am having a problem down below. I can't seem to connect the constructor Lang properly to establish a concatenation.

cat :: Ord a => Lang a -> Lang a -> Lang a
cat (ws) (zs)  = [ws:zs | ws++zs, ws <-Lang, zs <-Lang]

Any help will be greatly appreciated!

Upvotes: 1

Views: 362

Answers (1)

Jon Purdy
Jon Purdy

Reputation: 55069

cat :: Ord a => Lang a -> Lang a -> Lang a
cat (ws) (zs)  = [ws:zs | ws++zs, ws <-Lang, zs <-Lang]

This has several syntactic and type errors.

  • [… | ws ++ zs, …] tries to use ws ++ zs as a filter for the list comprehension, but ws ++ zs is of type Lang a, not Bool

  • [… | …, ws <- Lang, zs <- Lang] shadows the parameters ws and zs with new local variables bound inside the comprehension; in addition, Lang is a type constructor, not a list, so you can’t iterate over it

  • ws : zs assumes ws is an a and zs is a [a], since the (:) operator prepends an element to a list, but you’re trying to work with LOL a values

  • The Ord constraint is unnecessary, since you don’t use any comparison functions in the definition of cat

If you’re trying to concatenate every list (of type LOL a) from one Lang with every list from the other Lang, you need to do something like the following:

cat :: Lang a -> Lang a -> Lang a
cat ws zs = [catLol w z | w <- ws, z <- zs]

catLol :: LOL a -> LOL a -> LOL a
catLol (LOL m xs) (LOL n ys) = LOL (m + n) (xs ++ ys)

That is:

  • w :: LOL a is bound to each element of ws

  • Within that loop, z :: LOL a is bound to each element of zs

  • The two LOL a values are concatenated using catLol

  • catLol pattern matches on both its arguments to extract the length and list fields

  • catLol returns a combined LOL with a length equal to the sum of the lengths of its operands, and items resulting from concatenating their list fields

This can of course be written without the catLol helper function:

cat :: Lang a -> Lang a -> Lang a
cat ws zs = [LOL (m + n) (xs ++ ys) | LOL m xs <- ws, LOL n ys <- zs]

But if you’re trying to just concatenate the two Lang a values, cat is equal to (++), since they’re lists already:

-- Identical to: cat :: [LOL a] -> [LOL a] -> [LOL a]
cat :: Lang a -> Lang a -> Lang a
cat ws zs = ws ++ zs

If you want to normalise the result, then the Ord constraint makes sense to add back in, and you can just call your norm function, assuming it has type (Ord a) => Lang a -> Lang a:

cat :: (Ord a) => Lang a -> Lang a -> Lang a
cat ws zs = norm (ws ++ zs)

Upvotes: 1

Related Questions