<div dir="ltr"><div>Hi,</div><div><br></div><div>I'm teaching myself Haskell and attempting to use it for day-to-day tasks at work. I signed up for this list a few weeks ago, and this is my first post. Here's my problem:</div><div><br></div><div>I'm given a list of 45 Strings, each nine Chars long. The only characters are 'A', 'C', 'G' and 'T'. (This is for a bioinformatics application.) I'll refer to any nine-length String composed of these Chars as a "9-mer".<br></div><div><br></div><div>I need to generate a larger list of 9-mers such that no two 9-mers have a Levenshtein distance of less than 3. (The list I start with satisfies this requirement.)</div><div><br></div><div>I can generate as many 9-mers as I possibly can, but this process is very slow. It's also not being computed lazily; calling head on the output list forces the entire list of 9-mers to be computed. <b>I'd like to understand why this list isn't being computed lazily, and how I can change my code to make it so. </b>My knowledge of monads is pretty poor as well, so a digression or a series of questions about why the line <font face="monospace, monospace">[9] >>= (`replicateM` "ACGT")</font> works would also be helpful, as would general tips about writing clean code.</div><div><br></div><div>This is an O(n^2) operation, so I'm not expecting it to be slow. However, I figured that I'd just be able to take the first N elements from the output list.</div><div><br></div><div>Here's what I have:</div><div><br></div><div><font face="monospace, monospace">import Control.Monad</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">main :: IO ()</font></div><div><font face="monospace, monospace">main = interact processData</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">processData :: String -> String</font></div><div><font face="monospace, monospace">processData = unlines . (`merge` ([9] >>= (`replicateM` "ACGT"))) . lines</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">-- Merges two lists of things into a single list</font></div><div><font face="monospace, monospace">merge :: Eq a => [[a]] -> [[a]] -> [[a]]</font></div><div><font face="monospace, monospace">merge xs [] = xs</font></div><div><font face="monospace, monospace">merge xs ys = merge ((head ys) `addInto` xs) $ tail ys</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">-- Adds a thing into a list if it is "different" enough</font></div><div><font face="monospace, monospace">addInto :: Eq a => [a] -> [[a]] -> [[a]]</font></div><div><font face="monospace, monospace">y `addInto` ys =</font></div><div><font face="monospace, monospace">  if ((minimum $ map (dist y) ys) < 3)</font></div><div><font face="monospace, monospace">    then ys</font></div><div><font face="monospace, monospace">    else y:ys</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">-- Calculate the Levenshtein distance</font></div><div><font face="monospace, monospace">-- Lloyd Allison algorithm. See Haskell wiki</font></div><div><font face="monospace, monospace">-- code omitted</font></div><div><font face="monospace, monospace">dist :: Eq a => [a] -> [a] -> Int</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="arial, helvetica, sans-serif">My workaround to getting a smaller subset of the whole list is to replace </font></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:monospace,monospace">[9] >>= (`replicateM` "ACGT")</span></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">with</font></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:monospace,monospace">take 10000 $ </span><span style="font-family:monospace,monospace">[9] >>= (`replicateM` "ACGT")</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div>Thanks!</div><div>Mason Lai</div></div>