I'm struggling with Haskell, and the idea of using recursion to iterate over things.
For instance, how would
// this might seem silly but I need to do it
list1 = empty list
list2 = list of numbers
for i from 0 to N // N being a positive integer
for each number in list2
if number == i, add to list1
translate into the 'functional paradigm'? Any guidance would be appreciated.
Sorry, but I can't help but use a better algorithm...
let goodNumber n = (0 <= n && n < N)
let list1 = sort (filter goodNumber list2)
Edit: In hindsight this is a little bit of overkill, since the OP was trying to implement a sorting algo in the first place.
Going step by step:
list2 = list of numbers
We'll take this as a given, so list2 is still just a list of numbers.
for i from 0 to N // N being a positive integer
The correct way to do this in Haskell is generally with a list. Laziness means that the values will be computed only when used, so traversing a list from 0 to N ends up being the same thing as the loop you have here. So, just [0..n] will do the trick; we just need to figure out what to do with it.
for each number in list2
Given "for each" we can deduce that we'll need to traverse the entirety of list2 here; what we do with it, we don't know yet.
if number == i, add to list1
We're building list1 as we go, so ideally we want that to be the final result of the expression. That also means that at each recursive step, we want the result to be the list1 we have "so far". To do that, we'll need to make sure we pass each step's result along as we go.
So, getting down to the meat of it:
The filter function finds all the elements in a list matching some predicate; we'll use filter (== i) list2 here to find what we're after, then append that to the previous step's result. So each step will look like this:
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
That handles the inner loop. Stepping back outwards, we need to run this for each value i from the list [0..n], with the list1 value being passed along at each step. This is exactly what fold functions are for, and in this case step is exactly what we need for a left fold:
list2 :: (Num a) => [a]
list2 = -- whatever goes here...
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
list1 :: (Num a) => a -> [a]
list1 n = foldl step [] [0..n]
If you're wondering where the recursion is, both filter and foldl are doing that for us. As a rule of thumb, it's usually better to avoid direct recursion when there are higher-level functions to do it for you.
That said, the algorithm here is silly in multiple ways, but I didn't want to get into that because it seemed like it would distract from your actual question more than it would help.
concatMap instead of folding over an explicit concatenation step?
concatMap.let list1 = sort [a | a<-list2, a>=0, a<=N]
a<-list2 picks up each number of list2
a>=0, a<=N check if the picked number meets ALL these conditions
if conditions are met, a is put into a new list
Once all the elements of list2 have been thus checked and put into a new list, we do a sort on this
Resulting list is assigned to list1
