7

I don't have a particular coding problem on hand this is just an excercise to improve my thought process.

Few months back I started learning about functional programming( mostly in R) and I fell in love with it. Once in a while I try to think of problems that might be(correction: that I might find) difficult to solve in FP. Recently I thought of a situation where I might be more interested coding using imperative programming.

It seems to me that all higher order functions like map or reduce will iterate over whole list provided to them which makes sense. How would you avoid iterating over whole list in functional programming for whatever reason - ex. list is too long, list is actually an infinite series, evaluating each item is very expensive etc.

So to make this problem more specific lets say I have an array and I want to return every member from zeroth member to first element whose value is greater than 10, but I want to stop searching through the list once I find that element greater than 10.

How would you solve this?

Example array: 1 2 3 1 2 3 11 1 2 3 1 2 3

I'm not looking for answer specifically in R I've seen enough Haskell & Scala to usually make sense of the code.

EDIT:

I forgot to mention why I would rather use imperative programing here. I find that it is easier to stop iterating through array above with while/until loops because once I reach my terminating condition interpreter exits the loop, but map does not retain information about previous elements, and reduce solves that but I continues to iterate to the end of my list.

  • takeWhile (<= 10) in Haskell? I'm not sure what's your question. What does it have to do with "best practices", and why would that be hard in a functional programming language? – Vincent Savard Feb 20 '18 at 19:52
  • 1
    I never heard of takeWhile untill now but after quick google search I can see what you're getting at. Thanks – sgp667 Feb 20 '18 at 19:55
13

What you want to read more about is lazy evaluation. This basically means waiting until the last possible minute to do some work. So if you have the following Haskell code:

takeWhile (<= 10) $ map (+1) [1..]

[1..] is an infinite list, which you add 1 to every element, then take as many items in the list that are <= 10. However, the adding of one is done on demand, so you don't have to map the entire infinite list in order to get your result.

Haskell is lazy by default. In most all other languages, you have to explicitly request laziness. In Scala, that's done by using a lazy collection like a view, stream, or iterator. I don't know R.

  • Good answer. You might also want to mention Clojure, which, afaik, has good support for lazy collections. – Giorgio Feb 21 '18 at 12:27
  • @Giorgio the default return of many of the core clojure methods is a seq which is indeed lazy. Clojure as a whole though has eager evaluation. If you put an expression in the flow of execution, it'll get executed even if the expression's value isn't used. – Jared Smith Feb 22 '18 at 21:40
  • 1
    @JaredSmith: I know that Clojure uses eager evaluation but the question seems to be focuses on lazy collections, not on lazy evaluation in general. However, IMO you pointed out an important distinction: having extensive support for lazy collections does not mean that the language is lazy in general. – Giorgio Feb 23 '18 at 12:51
  • @Giorgio I actually prefer clojure's approach: having lazy collections gets you ~90% of the benefits of laziness. Although given how often the "why isn't println showing my stuff" question shows up in the clojure tag, maybe it gets you 90% of the confusion as well :) – Jared Smith Feb 23 '18 at 14:23
1

Edit : This is not a best practice sorry ! Here only an example of how to do it manually in a functional approach. Best practice is of course to use available ready to use high order function to do that.

An example in ocaml implementing by hand the loop for a list :

    let takewhile l f =
      let rec loop a l =
        match l with
        | [] -> a
        | hd :: tl ->
          if (f hd)
            then hd :: a else
            loop (hd :: a) tl in
      loop [] l 
      |> List.rev
  • The OP is asking for "best practise". can you explain how your answer is the best way to do it? – Mawg Mar 14 '18 at 8:31
  • 1
    I agree this would better be a comment than an answer about imperative believe. Sorry – Aldrik Mar 14 '18 at 8:35
  • 2
    It's a nice example (and code examples are difficult to fit into comments); it just doesn't answer the question of what is best practise & why? just add that to your answer – Mawg Mar 14 '18 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.