How to write a Haskell function looking up from a list of data

Question

I have a list of data that is read at runtime from a file and represented in tuples like this:

[(1,0.1),(2,0.2),(3,0.3)...etc...]

And I have written a function that takes a list and two integers as parameters and returns a double:

f :: [(Int,Double)] -> Int -> Int -> Double
f mylist i j
    | j < n = (do some stuff)
    | otherwise = max (f mylist (i-1) j) (some other stuff with m_i and p_i)
    where m_i = fst $ mylist !! (i-1)
          p_i = snd $ mylist !! (i-1)

Now, I'm new to Haskell and the concepts of pure functions, but since the list is static (it doesnt change) I am wondering if I really need to pass my list into the function?

Is it bad practise to pass big lists through umpteen layers of recursion?

Given I read the list at runtime, can I 'set up' two functions m and p to use them like this ?

f :: Int -> Int -> Double
f i j
    | j < n = (do some stuff)
    | otherwise = max (f (i-1) j) (some other stuff with m_i and p_i)
    where m_i = m (i-1)
          p_i = p (i-1)

And if so, how can I set up the m and p functions (which are pure, right?) to essentially return values that I read from a file at run time (which is unpure, if I understand correctly).

Thanks for any Help!

Answer 1

How to use 2 function per 1 list - use map and make, for example, a tuple

result :: (a->b) -> (a->c) -> [a] -> [(b,c)]
result m p = map (\elem -> (f elem , p elem) )  list

If you pass list as a parameter - is nothing bad. If you don't use it - it won't be read by compiler. But complexity of algorithm matters.

Answer 2

Is it bad practise to pass big lists through umpteen layers of recursion?

Seems like conceptually you're worried about making copies of the large list which isn't the case, Haskell will address the same data structure through the recursion. You don't need to explicitly lift it out.

Using explicit (!!) may cause some issues, least of which because its a partial function. Since you're doing a linear sweep of the data it might be worth the time to try and phrase your problem as a map or fold, or some combination thereof. If you can do that you open up a lot of optimizations to the compiler.

Also strongly recommend looking into the vector library.

http://hackage.haskell.org/package/vector-0.10.0.1

Answer 3

Yes your list is immutable, but it's not known at compile time. So you have two choices

1. Pass the list
2. Pass a function which knows about this list and will give you it's values at indices

Notice that these are conceptually equivalent, both involve you passing some data to represent a list of values, it's just a question of how you represent it.

So p and m would look like

 myList = ...
 p i = fst $ myList !! i
 m i = fst $ myList !! i

Which really doesn't buy you much.

If it makes you feel better, a list of 10000 elements costs the same to pass to a function (not to create) as a list of 3. It compiles to either the head + a pointer to the rest or a nil value. This is because Haskell has singly linked lists,

List a = Cons a (List a) -- Head, rest of list
       | Nil             -- End of list

So passing it by value is dirt cheap vs imperative arrays, but lookup time suffers correspondingly.

As a corollary to this, be awefully careful with that (!!). Consider whether your problem is better stated as a fold or map. Using higher order combinators is very Haskelly :)

Answer 4

It's not really bad practice to recurse on big lists, though there are some gotchas. Generally, as long as your recursive functions are incrementally productive you'll be fine (O(1) memory, O(n) time) even with really large lists.

In your case, you seem to be reading the list backwards since your index value recurses downward. This means that you'll have to load the entire list into memory in order to reverse it---perhaps it's better to store the list reversed?

If you're reading from a file you are almost certainly impure. There are some cases when it might be valuable to pretend like it's a pure operation, but usually it's better to pass this stuff forward to IO-based early setup/configuration steps.

For instance, my executable might look like this

main :: IO ()
main = do bigList <- readFileSomehow -- this is impure
          let res = f bigList        -- this is pure
          print res                  -- this is impure again

Here we're using do syntax to extract the bigList :: [(Int, Double)] from the impure file reading as a first step. Then we immediately pass that bigList into the pure function f and get a pure result res. Finally, we run the impure print action on the pure res.

This lets us isolate all the impurity to our main function and write f completely independently from niggling impure details like "how" we arrived at that large input to begin with.

---

It's possible to abstract the notion of this list even further using the m and p functions you describe. All they're doing is hiding the list and allowing it only to be accessed via (!!).

inner :: Int -> Int -> (Int -> Int) -> (Int -> Double) -> Something

outer :: [(Int, Double)] -> Int -> Int -> Something
outer bigList i j = inner i j (\ix -> fst $ bigList !! ix) (\ix -> snd $ bigList !! ix)

where outer now "wraps" inner preventing it from seeing bigList except via those two indexing functions.

---

Finally, this entire method doesn't have a terrifically "Haskelly" feeling, unfortunately. Explicit recursion using (!!) on big lists tends to lead to slowdowns and code duplication. It's almost always a better idea to try to formulate your intentions in terms of maps and foldrs if possible.

Answer 5

In short, no.

If you are reading the list from a file, then it will not be pure, and there will be no way to use it from a pure function without passing it to that pure function.

Reading the list from a file means the result of reading and parsing it is IO [(Int,Double)]. You cannot "extract" the value from IO; you can only introduce the pure function into IO, for example, using fmap or bind.

To illustrate:

main = do
         ...
         xs <- readFile -- this is IO String
         let mylist = parse xs -- whatever conversion
                               -- from String to [(Int,Double)]
         -- mylist cannot live outside this IO
         let zs = f mylist i j -- so got to pass it to f
         ...