# Instances for partial conversion functions

**URL:** <https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692>\
**Category:** Learn\
**Created:** [January 31, 2024, 9:35pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692 "2024-01-31T21:35:10Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![NicolasT](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/nicolast/32/2872_2.png) [@NicolasT](https://discourse.haskell.org/u/NicolasT)\
**Post date:** [January 31, 2024, 9:35pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/1 "2024-01-31T21:35:10Z")

</div>

Hello,

In a project, I have some universal type `Object` for which conversion functions to “more concrete” types can be implemented. Parsers, in a sense.

A basic parser into type `a` would be a function of type `Object -> Maybe a`, but so these can be combined, a `Parser a` is really a `[Object -> Maybe a]` where, when executed on some `Object`, the first `Just` value “wins” (see code below). This allows for definitions like

```haskell
intParser :: Parser Int = _
floatParser :: Parser Float = _

intOrFloatParser :: Parser (Either Int Float)
intOrFloatParser = fmap Left intParser <|> fmap Right floatParser

```

Note in the above I used `fmap` (`Functor`) and `<|>` (`Alternative`). Indeed, instances for these typeclasses seem quite straight-forward, and I believe the implementations are law-abiding. However, `Alternative` has an `Applicative` constraint, and that’s where I’m stuck: where `pure` is easy to define, I’m unable to figure out what a sensible implementation of `<*>` (or `liftA2`) would look like, given the semantics of a `Parser` (and what the effects of such implementation would be). Similarly, a `MonadPlus` instance seems straight-forward given the `Alternative` instance, but there as well I don’t see what `Monad`'s `>>=` would be.

Does the `[T -> Maybe a]` type ring any bells, and/or does anyone see if/which sensible implementations for `<*>` and `>>=` could be provided?

For reference, some code to make the idea more concrete:

```haskell
module Parser where

import Control.Applicative (Alternative(..))
import Control.Monad (MonadPlus(..))
import Data.Monoid (First(..))

data Object

-- | A 'Parser a' is a list of functions which may be able to convert an
-- 'Object' into an 'a'. When executed using 'runParser', the first
-- successful conversion result is returned.
newtype Parser a = Parser [Object -> Maybe a]

runParser :: Parser a -> Object -> Maybe a
runParser (Parser a) obj = getFirst $ foldMap (First . ($ obj)) a

instance Functor Parser where
    fmap f (Parser a) = Parser $ fmap (fmap f .) a

instance Applicative Parser where
    pure a = Parser $ pure (const $ Just a)
    a <*> b = _ -- ???

instance Alternative Parser where
    empty = Parser mempty
    Parser a <|> Parser b = Parser (a <> b)

instance Monad Parser where
    a >>= k = _ -- ???

instance MonadPlus Parser where
    -- Could rely on default implementations, but to be more explicit...
    mzero = empty
    mplus = (<|>)

instance Semigroup (Parser a) where
    (<>) = (<|>)

instance Monoid (Parser a) where
    mempty = empty

```

Thanks in advance!

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [January 31, 2024, 10:18pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/2 "2024-01-31T22:18:37Z")

</div>

Your parser type is a composition of functors, all of which are monads:

```haskell
import GHC.Generics ((:.:))
type Parser = [] :.: (((->) Object) :.: Maybe)

```

so you can at least get an `Applicative` instance for free, since `Applicative` functors are closed under composition. Since the outermost Functor is an Alternative, the whole composition is. The Generics module provides the necessary derivation.  
Not all compositons of monads are monads, though. Especially `[]` is hard to deal with since it is a non-commutative monad.

---

<div class="post-metadata">

**Author:** ![NicolasT](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/nicolast/32/2872_2.png) [@NicolasT](https://discourse.haskell.org/u/NicolasT)\
**Post date:** [January 31, 2024, 10:41pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/3 "2024-01-31T22:41:45Z")

</div>

Thanks for this. I was looking into the instances of `[]` and `a -> b` earlier, but got quite confused by the `[]` one in this context: in essence, my `Parser` type “behaves” much more as a function than as a list, hence `zip`ing seems not to make much sense? Or maybe I’m missing something/confusing things?

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [January 31, 2024, 10:51pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/4 "2024-01-31T22:51:36Z")

</div>

The inner Applicative `((->) Object) :.: Maybe` is actually a monad, a.k.a. `ReaderT Object Maybe`. Hence the question about the entire thing being a monad boils down to a monad instance for types like `[] :.: m` for `m` some monad. We already have `pure` so only `>>=` remains to be defined, or equivalently a

```haskell
join :: [m [m a]] -> [m a]

```

This `join` you could get by virtue of a distributive law

```haskell
m [a] -> [m a]

```

but in our case I think we are out of luck: I can not imagine a sensible function

```haskell
(Object -> Maybe [a]) -> [Object -> Maybe a]

```

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [January 31, 2024, 10:59pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/5 "2024-01-31T22:59:07Z")

</div>

> [@NicolasT](#):
>
> in essence, my `Parser` type “behaves” much more as a function than as a list

That is because the list is only making choices explicit.  
Why not:

```haskell
import Control.Monad.Reader (ReaderT)
type Parser = ReaderT Object Maybe

```

which is already an Alternative because `Maybe` is. Its implementation does what you want, I think: `p <|> q` applies both `p` and `q` to the same object and combines both results using the Alternative instance of `Maybe` which chooses the first `Just` result if any.

---

<div class="post-metadata">

**Author:** ![NicolasT](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/nicolast/32/2872_2.png) [@NicolasT](https://discourse.haskell.org/u/NicolasT)\
**Post date:** [January 31, 2024, 11:11pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/6 "2024-01-31T23:11:49Z")

</div>

Agreed, a `Monad` instance is likely not possible because there’s likely no sensible “and then” operation, given there’s only a single input value.

---

<div class="post-metadata">

**Author:** ![NicolasT](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/nicolast/32/2872_2.png) [@NicolasT](https://discourse.haskell.org/u/NicolasT)\
**Post date:** [January 31, 2024, 11:13pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/7 "2024-01-31T23:13:34Z")

</div>

The actual code is quite a bit more elaborate, where the base parsers are not simple `Object -> Maybe a` functions, and I need all possible parser functions in a list eventually for further processing. The code above is an oversimplification. So reusing `ReaderT` as-is won’t fly (it definitely would in the demo code, though, thanks for pointing that out!)

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [January 31, 2024, 11:17pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/8 "2024-01-31T23:17:08Z")

</div>

If you really need list choices embedded, consider a proper [ListT transformer](https://hackage.haskell.org/package/list-t).

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [February 1, 2024, 2:16am UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/9 "2024-02-01T02:16:06Z")

</div>

> [@NicolasT](#):
>
> ```haskell
> -- [...] When executed using 'runParser', the first
> -- successful conversion result is returned.
> 
> ```

That _seems_ to resemble how these work:

[Functional Pearl: Parallel Parsing Processes](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/0AF17481A41F2007752F530F07698139/S0956796804005192a.pdf/functional_pearl_parallel_parsing_processes.pdf) (2004)

…but looking at that type declaration again:

> [@](#):
>
> ```haskell
> newtype Parser a = Parser [Object -> Maybe a]
> 
> ```

has got me thinking - if all the list’s elements are being applied to the same `Object`, then:

> [@](#):
>
> ```haskell
> newtype Parser a = Parser (Object -> [Maybe a])
> 
> ```

could be a simpler option.

---

<div class="post-metadata">

**Author:** ![rhendric](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/rhendric/32/2689_2.png) [@rhendric](https://discourse.haskell.org/u/rhendric)\
**Post date:** [February 1, 2024, 2:35am UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/10 "2024-02-01T02:35:12Z")

</div>

> [@NicolasT](#):
>
> I need all possible parser functions in a list eventually for further processing.

Can you elaborate on this? I anticipate that there’s a way to twiddle your data structures to capture what you want without mixing the list and the type parameter (which is what prevents this from being a relatively straightforward monad transformer stack—even a correct ListT can have some surprising behavior, and I generally advise people to avoid it when something simpler will do).

---

<div class="post-metadata">

**Author:** ![tobz619](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tobz619/32/3125_2.png) [@tobz619](https://discourse.haskell.org/u/tobz619)\
**Post date:** [February 4, 2024, 6:22pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/11 "2024-02-04T18:22:29Z")

</div>

My first feeling is that you’d wrap what you’re interested in a type.

```haskell
data ObjectValue = ObjInt Int | ObjFloat Float ...
type Parser = Object -> Maybe ObjectValue 

```

And then you could combine all your parsers with [asum](https://hackage.haskell.org/package/base-4.19.0.0/docs/Control-Applicative.html#v:asum)

```haskell
numParsers :: [Object -> Maybe ObjectValue]
numParsers = [intParser, floatParser ...]

runNumParsers :: Object -> Maybe ObjectValue
runNumParsers = asum numParsers 

```

First one succeeds, no success returns `Nothing`.

Then you would unwrap your types and values as needed.

My apologies if I have misunderstood the question.

Edit: I think you’re trying to write a generalized instance for the more complicated [Object → Maybe a] type. And I think that’s way above my skill level.

---

<div class="post-metadata">

**Author:** ![NicolasT](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/nicolast/32/2872_2.png) [@NicolasT](https://discourse.haskell.org/u/NicolasT)\
**Post date:** [February 4, 2024, 6:29pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/12 "2024-02-04T18:29:20Z")

</div>

Thanks again for all insights. I guess I got confused mainly by the use of a list (which is needed because of implementation detail reasons only, heck, the actual code isn’t even Haskell…), but failed to realize this thing is defined not by its implementation, but by its behaviour, which is in a sense fully dictated by `runParser`.

Thanks to some of the comments here, I started to realize the actual type is a bit like `newtype Parser a b = Parser (a -> Alt Maybe b)`, and the `Applicative`, `Monad` and other instances of `a -> b` can be reused (in spirit).

I actually defined it as `newtype Parser a b = Parser [a -> Maybe b]` not to get confused by this `Object` thing, with (next to the one above) the following instances:

```haskell
instance Applicative (Parser a) where
    pure a = Parser [\_ -> Just a]
    pf <*> pa = Parser [\a -> case runParser pf a of
      Nothing -> Nothing
      Just f -> case runParser pa a of
        Nothing -> Nothing
        Just v -> Just (f v)]

instance Monad (Parser a) where
    f >>= k = Parser [\a -> case runParser f a of
      Nothing -> Nothing
      Just a' -> runParser (k a') a]

instance MonadFail (Parser a) where
    fail _ = Parser []

```

Then, I wanted to check whether laws hold. Since my datatype contains functions, it’s not obvious how to achieve this (since it’d essentially mean I’d need to prove equality of functions, at some point). However, using the excellent [`quickcheck-higherorder`](https://hackage.haskell.org/package/quickcheck-higherorder) library I was able to express the `Functor`/`Applicative`/`Alternative`/`Monad`/`MonadFail`/`MonadPlus` laws, a bit as is done in [`quickcheck-classes`](https://hackage.haskell.org/package/quickcheck-classes) (which can’t handle higher-order types), and at least QuickCheck seems to believe my instances are OK, when both side of the `Equation`s (expressions of laws) are QuickCheck’ed themselves over `runParser` for some random instantiation of `a` and `b`.

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [February 6, 2024, 7:42am UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/13 "2024-02-06T07:42:17Z")

</div>

I it suspicious that in all your definitions you use the idiom  
`[\a -> case runParser ...]` so every usage of `<*>` or `>>=` will collapse the list layer into a singleton. That may also be the reason why your QuickCheck tests succeed. Are you sure you want this?  
The law `m >>= return = m` ought to be violated. Please check with a list input of length \> 1.

Typically, transformer stacks including a list layer tend to obey all the laws except that the list order is not respected. As long as you don’t care about the order of options, then you may be fine. But since your `runParser` tries all choices from left to right, list order is actually important.

As an example, consider finite probability distributions.

```haskell
import Data.Monoid (Product(..))
type Dist a = [(Product Double,a)]
dirac = pure . pure :: a -> Dist a
bind :: Dist a -> (a -> Dist b) -> Dist b
bind dx k = do
    (p,a) <- dx
    map ((p,id) <*>) (k a)

prob :: (a -> Bool) -> Dist a -> Product Double
prob event = foldMap (\(p,a) -> if event a then p else mempty)

```

This is a lawful monad by virtue of `return = dirac`, `(>>=) = bind` but only disregarding the list order, that is, w.r.t the semantics given by `prob`.

---

<div class="post-metadata">

**Author:** ![NicolasT](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/nicolast/32/2872_2.png) [@NicolasT](https://discourse.haskell.org/u/NicolasT)\
**Post date:** [February 6, 2024, 8:18pm UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/14 "2024-02-06T20:18:00Z")

</div>

I believe the list is a red herring. Indeed, `m >>= return = m` doesn’t hold at a structural level, but does at the effects/interpretation level: imagine the type itself is abstract, you don’t know about the list layer (which is only used by/because of `<|>`), then it’s fully isomorphic to `Object -> Maybe a` (also witnessed by `runParser`s type). Basically, if I wouldn’t use the list and instead actually use `Object -> Maybe a` as the type, then `<|>` would be implemented more “directly” of course, and `<*>` and `bind` would be ± what my implementation does, without wrapping the resulting function in a singleton list.

As for the correctness of the `Applicative` and `Monad` instances: the version abstracting over the input type, hence `type Parser a b = a -> Maybe b` (or, in my case, with the list but “abstract”) is a profunctor, and looking into the `profunctors` package I came by [`Star`](https://hackage.haskell.org/package/profunctors-5.6.2/docs/Data-Profunctor.html#t:Star), which is `newtype Star f d c = Star (d -> f c)`, i.e., my `Parser a` is `Star (Alt Maybe) Object a`, and `Star f d`s `Applicative`, `Monad` and other instances are very much alike the ones I have for `Parser a`.

Finally, I found [this blog post](http://jackkelly.name/blog/archives/2020/11/03/profunctor_decoders_optical_decoders/index.html): looks like I’m not the first exploring this area.

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [February 7, 2024, 6:50am UTC](https://discourse.haskell.org/t/instances-for-partial-conversion-functions/8692/15 "2024-02-07T06:50:34Z")

</div>

Yeah I guess in the end you have choices of which composing library (mtl, `Compose`, Generic `:.:`) you use to build your result functor and whether to wrap the parser in a `Star`, `Kleisli` or similar. The class instances provided by each library will likely give you slightly different ergonomics.

> [@olf](#):
>
> `Applicative` functors are closed under composition

At least Applicative and Alternative are a no-brainer but since the Monad instance is unlawful you should be careful whether GHC uses the monad laws to optimize your code while changing the semantics. I’m unsure whether that is actually a real danger.