How does this snippet translate to Haskell?

Question

I am struggling with Haskell, and the idea is to use recursion to iterate over things.

For example, how

// 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 a "functional paradigm"? Any recommendations would be appreciated.

Answer 1

Step by step:

 list2 = list of numbers 

We will consider this as given, so list2 is 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 usually with a list. Laziness means that the values ​​will be calculated only when they are used, so moving the list from 0 to N ends with the same as the loop that 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 everyone", we can conclude that here we need to go through the whole list2 ; what we do with it, we do not know yet.

 if number == i, add to list1 

We build list1 as we go, so ideally we want this to be the end result of the expression. It also means that at every recursive step we want the result to be list1 , which we have “so far”. To do this, we need to make sure that we go through each step as we move.

So, down to the meat:

The filter function finds all elements in the list corresponding to a certain predicate; we will use filter (== i) list2 here to find out what we need, and then add to the previous result. Therefore, each step will look like this:

 step :: (Num a) => [a] -> a -> [a] step list1 i = list1 ++ filter (== i) list2 

This handles the inner loop. Going back, we need to run this for every value i from the list [0..n] , and the value list1 is passed at each step. This is exactly what the bending functions are for, and in this case step exactly what we need for the 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 do this for us. As a general rule, it is usually best to avoid direct recursion when there are higher level functions to do this for you.

---

However, the algorithm here is stupid in many ways, but I didn’t want to delve into it because it seemed like it would distract your real question more than it would help.

Answer 2

Sorry, but I can not help but use the best algorithm ...

 let goodNumber n = (0 <= n && n < N) let list1 = sort (filter goodNumber list2) 

---

Edit: In retrospect, this is a bit overkill, since the OP tried to implement the sorting algorithm in the first place.

Answer 3

 let list1 = sort [a | a<-list2, a>=0, a<=N] 

a<-list2 selects each number list2 a>=0, a<=N to check whether the selected number meets all these conditions if the conditions are met, a is placed in a new list After all the elements of list2 have been checked and placed in a new one list, we pretend on this The resulting list is assigned to list1