title: Frequency Count in Haskell
body: <p>So The task i'm trying to accomplish is to get a frequency list of all possible patterns of length n from a string s.</p>
  
  <pre><code>Input (Text,Length) 
  Output (Frequency)
  String -&gt; Int -&gt; [Int]
  freqCount s n = frequency list [int] in alphabetical order
  </code></pre>
  
  <p>["A","B","C","D"]</p>
  
  <p>where the characters in s are limited to the four mentioned above, so I figured first step would be to get all the possible permutations of length n with repetitions allowed.</p>
  
  <pre><code>permutationsR k = sort(replicateM k ['A','B','C','D'])
  </code></pre>
  
  <p>eg. </p>
  
  <pre><code>permutationsR 2 
  </code></pre>
  
  <p>would give the output</p>
  
  <pre><code> ["AA","AB","AC","AD","BA","BB","BC","BD","CA","CB","CC","CD","DA","DB","DC","DD"]
  </code></pre>
  
  <p>and then for each pattern get a count of how many times each occurred
  so something like</p>
  
  <pre><code>patternCount:: String -&gt; String -&gt; Int
  patternCount text pattern = length (filter (\x -&gt; x == pattern) [take (length(pattern)) (drop x text)| x &lt;- [0..length(text)- length(pattern)]])
  frequencyCount s n = map (\x -&gt; patternCount s x) (permutationsR n)
  </code></pre>
  
  <p>However i figure this is going to be extremely inefficient because I am essentially going through the entire list to check for each pattern length(permutationsR n) times instead of what I reason should be possible to do in only one iteration.</p>
  
  <p>Is there a way to generate a frequency map like i would in an imperative language.</p>
  
  <p>i.e. in pseudocode</p>
  
  <pre><code>where s = string
  and n = length of pattern
  //pattern is a map where key = pattern and value = frequencyCount
  
  patterns = {"AA":0,"AB":0,"AC:0...}
  for (i = 0; i &lt; (length s - n); i++){
      patterns[s[i:(i+n)]] += 1
  }
  </code></pre>
  
  <p>basically just iterating through once, splitting the string from (i:i+n)
  and updating the patterns map with each occurence.</p>
  
  <p>example input,output would be something like this</p>
  
  <pre><code>s= "AABBCA"
  n = 2
  frequencyList s n = [1,1,0,0,0,1,1,0,1,0,0,0,0,0,0,0]
  </code></pre>