CODEWITHSUNDEEP
listhaskellfunctional-programmingpattern-matching
Lana
Lana

Reputation: 1304

Building an exponentially sized list in haskell

I have two functions which only do something if C is a specific pattern. Each function outputs a list of C.

My goal is, given [C], I want to get all possibilities of calling f1 and f2 on the list while leaving the rest unchanged. For example:

suppose the list of C is:

    c1
    c2 --matches the pattern
    c3

then I want a list of two lists

[[c1] ++ (f1 c2) ++ [c3],[c1] ++ (f2 c2) ++ [c3]]

However, if I have

c1
c2 --matches the pattern
c3 --matches the pattern

Then we should have 4 lists because we want all combinations of calling f1 and f2. So it would be:

[(f1 c1) ++ (f1 c2) ++ [c3], (f2 c1) ++ (f2 c2) ++ [c3], 
(f1 c1) ++ (f2 c2) ++ [c3], (f2 c1) ++ (f1 c2) ++ [c3]]

currently, my code is structured roughly in the following way:

f1 :: C -> [C]

f2 :: C ->  [C]

combine ::  [C] -> [[C]]
combine  my_pattern:xs =  ?
combine (x:xs) =  ?
combine [] = []

  where first_set = (f1 my_pattern)
        second_set = (f2 my_pattern)

Could someone give intuition on how I could fill the remaining part? Is there any functions from Data.List that can be useful? I looked at the documentation, but wasn't able to immediately notice which one could be helpful.

Upvotes: 1

Views: 152

Answers (3)

Daniel Wagner
Daniel Wagner

Reputation: 152707

The other answers seem very complicated to me. In this answer I will expand on my comment: this is just a foldMap combining the nondeterminism monad (lists!) with the sequence monoid (lists!).

First write a thing that works on a single element of the list:

singleElement x
    | matchesThePattern x = [f1 x, f2 x]
    | otherwise = [[x]]

Then apply it to each element:

import Data.Monoid
combine = foldMap (Ap . singleElement)

That's it. That's the whole code.

For example, suppose we want to repeat each letter either 2 or 3 times, i.e. x -> xx or xxx, and all other characters to stay the same.

singleElement x
    | 'a' <= x && x <= 'z' = [[x, x], [x, x, x]]
    | otherwise = [[x]]

Then we can try it in ghci:

> combine "123def"
Ap {getAp = ["123ddeeff","123ddeefff","123ddeeeff","123ddeeefff","123dddeeff","123dddeefff","123dddeeeff","123dddeeefff"]}

Pick a better name than singleElement in your own code, of course.

Upvotes: 2

Will Ness
Will Ness

Reputation: 71065

You must have

applicable_f1 :: C -> Bool
applicable_f2 :: C -> Bool

defined somehow. Then,

combinations :: [C] -> [[C]]
combinations cs = map concat . sequence $
    [ concat $ [ [ [c]   | not (applicable_f1 c || applicable_f2 c)]
               , [ f1 c  | applicable_f1 c]
               , [ f2 c  | applicable_f2 c] ]
      | c <- cs]

Upvotes: 1

cole
cole

Reputation: 725

My approach would be to

  1. Solve the problem for the element in the list you're currently looking at (x or my_pattern). This means generating one or more new lists.
  2. Solve the problem for the rest of the list (xs). This will give you back a list of lists ([[C]]).
  3. Combine the two solutions. If you have multiple lists generated from step 1, each of these lists ([C]) will combine with each list (also [C]) in the list of lists ([[C]]) from step 2.

I have two possible approaches.

It isn't clear to me how much help you are looking for, so I've left my answers somewhat "spoiler free." Ask for clarification or more details if you need it.

List comprehension

Without delving into the weeds of the Applicative or Traversable typeclasses, you can accomplish what you want with a list comprehension.

Let's consider the case where your pattern is matched. I would write a list comprehension as follows:

[ x ++ y | x <- _, y <- _] :: [[C]]
-- this means
-- x :: [C]
-- y :: [C]
-- _ :: [[C]]

This list comprehension creates a list of lists. x is what is being prepended, so it would make sense for it to be coming from the application of the functions f1 and f2. y is the tail end of each resulting list. I'll leave you to figure out what it might be.

The non matching case is simpler than this, and can be written like

[ x : y | y <- _] :: [[C]]
-- note that x is not local to the list comprehension
-- y :: [C]
-- _ :: [[C]]

although this really is just a special case of the above list comprehension.

Applicative

Another way of approaching this problem would be by using the Applicative instance of [a].

Let's examine the function (<*>) under the list Applicative instance.

-- this is the type when specialized to lists
(<*>) :: [a -> b] -> [a] -> [b]

This function has a kind of strange type signature. It takes a list of functions, and a list, then returns you another list. It has the effect of applying each function a -> b to each element of [a] in order.

>>> [(+1), (+2)] <*> [1,2,3]
-- [2,3,4] comes from (+1)
-- [3,4,5] comes from (+2)
[2,3,4,3,4,5]

We want to get out [[C]], not [C], so if we want to use (<*>) we can specialize its type more to

(<*>) :: [a -> [C]] -> [a] -> [[C]]

To avoid confusion, I recommend picking a = [C], which gives

(<*>) :: [[C] -> [C]] -> [[C]] -> [[C]]

Your list of functions should be prepending the right elements onto the lists you're generating. The second argument should be the lists returned by a recursive call.

Upvotes: 1

Related Questions