How to interact with pure algorithm in IO code

Question

To illustrate the point with a trivial example, say I have implemented filter:

filter :: (a -> Bool) -> [a] -> [a]

And I have a predicate p that interacts with the real world:

p :: a -> IO Bool

How do it make it work with filter without writing a separate implementation:

filterIO :: (a -> IO Bool) -> [a] -> IO [a]

Presumably if I can turn p into p':

p': IO (a -> Bool)

Then I can do

main :: IO ()
main = do 
  p'' <- p'
  print $ filter p'' [1..100]

But I haven't been able to find the conversion.

Edited: As people have pointed out in the comment, such a conversion doesn't make sense as it would break the encapsulation of the IO Monad.

Now the question is, can I structure my code so that the pure and IO versions don't completely duplicate the core logic?

Sure it is, but as said this is just a contrived example. Is the general solution to always implement separately a version that interacts with IO ? That'll be a lot boilerplate code for any non-trivial algorithm. — Chris, Jan 23 '17 at 17:30
I think that would be against the use of `Monad`s. What `a -> IO Bool` means is that you feed as input a variable `a` and "it does some `IO` returning a bool". Now you want to convert that to "doing some IO returning the generic function". But in order to execute the function, one probably needs to do IO. The conversion makes - afaik - no sense at all. — Willem Van Onsem, Jan 23 '17 at 17:32
Take for instance the example `FilePath -> IO String` that reads from the file and returns it content. Now you want to convert that to `IO (FilePath -> String)`? Performing IO such that you have a function that - regardless of the filename you give it - returns you its content without performing IO anymore? Mind that for instance in Linux some files are technically drivers to which you write bytes. — Willem Van Onsem, Jan 23 '17 at 17:34
Make sense. Seems like there's no choice but to have a separate function signature. But surely there are some ways to share code between the two implementation? After all the only differences between the two are lifting things in and out of IO. — Chris, Jan 23 '17 at 17:39
indeed because a monad forces "order" so to speak, that `f` is called after `g` is called. And it can also depend on the previous call. A generic function `FilePath -> Maybe String -> IO String` could for instance act as a read/writer: if the `Maybe String` is `Just _`, the content is written to a file, so now the previous monadic call has *effects* on the next one. Because if you later decide to read from that file, the previous write will have modified something. A simple monad I sometimes use to conceptualize is the state monad: you carry a state with you and each function can read/write. — Willem Van Onsem, Jan 23 '17 at 17:41
It's not clear what you're asking. "to share code between the two implementation" do you mean to share code between `filter` and `filterM`? This sounds like either an X/Y problem (which we can't help you with without a proper example), or a hypothetical "gotcha" type question. — jberryman, Jan 23 '17 at 17:42
@jberryman: I think what the OP aims to do is "hack" the inner function out of `a -> IO b` and then use the *good old filter*. — Willem Van Onsem, Jan 23 '17 at 17:43
@jberryman the original question is about whether it's possible to do without having to write a IO version of the same function(the answer seems no). The question that I asked in the comment is given pure version of the function, can you implement the IO version without re-writing everything? I have concrete example but I don't think it adds anything to the underlying question. — Chris, Jan 23 '17 at 17:49
It is also worth noting that the impossibility of going from `a -> IO b` to `IO (a -> b)` that @WillemVanOnsem has explained reflects the difference between `Monad` and `Applicative`. — duplode, Jan 23 '17 at 18:20
This is a potential duplicate of http://stackoverflow.com/questions/27267848/turning-a-mb-into-ma-b , especially given the last question. — chi, Jan 23 '17 at 19:43
@chi Given how the question has evolved, I don't think it is quite a duplicate anymore. Still, your answer there covers very well the discussion in the comments here. — duplode, Jan 23 '17 at 19:49
@duplode Indeed, I intentionally did not vote this as a duplicate since that would close it at once. This question is more nuanced. — chi, Jan 23 '17 at 21:09

score 5 · Accepted Answer · edited Jan 23 '17 at 19:43

5

How do it make it work with filter without writing a separate implementation

That isn't possible and the fact this sort of thing isn't possible is by design - Haskell places firm limits on its types and you have to obey them. You cannot sprinkle IO all over the place willy-nilly.

Now the question is, can I structure my code so that the pure and IO versions don't completely duplicate the core logic?

You'll be interested in filterM. Then, you can get both the functionality of filterIO by using the IO monad and the pure functionality using the Identity monad. Of course, for the pure case, you now have to pay the extra price of wrapping/unwrapping (or coerceing) the Identity wrapper. (Side remark: since Identity is a newtype this is only a code readability cost, not a runtime one.)

 ghci> data Color = Red | Green | Blue deriving (Read, Show, Eq)

Here is a monadic example (note that the lines containing only Red, Blue, and Blue are user-entered at the prompt):

 ghci> filterM (\x -> do y<-readLn; pure (x==y)) [Red,Green,Blue]
 Red
 Blue
 Blue
 [Red,Blue] :: IO [Color]

Here is a pure example:

 ghci> filterM (\x -> Identity (x /= Green)) [Red,Green,Blue]
 Identity [Red,Blue] :: Identity [Color]

edited Jan 23 '17 at 19:43

Daniel Wagner

145,880
9
220
380

answered Jan 23 '17 at 18:16

Alec

31,829
7
67
114

Footnote: I wondered for a moment about whether there was a version of `filterM` generalised to `Applicative`; then I hoogled it and found [it is `filterM` itself](https://hackage.haskell.org/package/base-4.9.1.0/docs/Control-Monad.html#v:filterM)! – duplode Jan 23 '17 at 18:29
@Alec Thanks! The `Identity` monad is what I have been missing. – Chris Jan 23 '17 at 18:34
Minor correction: the pure example should also use `filterM` – Chris Jan 23 '17 at 18:51
@Chris Thanks! Important correction. - it is sort of the point of the question. :) – Alec Jan 23 '17 at 19:01
@duplode That bugs me so much... Only half the functions in `Control.Monad` have been generalized to `Applicative` and yet they all have the `M` suffix. – Alec Jan 23 '17 at 19:13

leftaroundabout · Answer 2 · 2017-01-23T19:41:16.240

As already said, you can use filterM for this specific task. However, it is usually better to keep with Haskell's characteristic strict seperation of IO and calculations. In your case, you can just tick off all necessary IO in one go and then do the interesting filtering in nice, reliable, easily testable pure code (i.e. here, simply with the normal filter):

type A = Int
type Annotated = (A, Bool)

p' :: Annotated -> Bool
p' = snd

main :: IO ()
main = do 
  candidates <- forM [1..100] $ \n -> do
      permitted <- p n
      return (n, permitted)
  print $ fst <$> filter p' candidates

Here, we first annotate each number with a flag indicating what the environment says. This flag can then simply be read out in the actual filtering step, without requiring any further IO.

In short, this would be written:

main :: IO ()
main = do 
  candidates <- forM [1..100] $ \n -> (n,) <$> p n
  print $ fst <$> filter snd candidates

While it is not feasible for this specific task, I'd also add that you can in principle achieve the IO seperation with something like your p'. This requires that the type A is “small enough” that you can evaluate the predicate with all values that are possible at all. For instance,

import qualified Data.Map as Map

type A = Char

p' :: IO (A -> Bool)
p' = (Map.!) . Map.fromList <$> mapM (\c -> (c,) <$> p c) ['\0'..]

This evaluates the predicate once for all of the 1114112 chars there are and stores the results in a lookup table.

How to interact with pure algorithm in IO code

2 Answers2