Flatten Maybe structure in Haskell-CodePudding

I thought join of Control.Monad had the same capability of Array.flat in JavaScript.

https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Array/flat

However, it's against my expectation and the actual behavior is

f :: Maybe a -> Maybe a
f = \a -> join (Just a) -- works as I expected

f' :: a -> Maybe a
f' = \a -> join (Just a) -- I thought it returns Maybe a
-- Occurs check: cannot construct the infinite type: a ~ Maybe a
-- Expected type: Maybe (Maybe a)     
-- Actual type:   Maybe a

Is there flatten function available instead or any workaround?

CodePudding user response：

What type would join have to have for your proposed f'?

f' :: a -> Maybe a
f' = \a -> join (Just a :: Maybe a) :: a

So, for that to typecheck, we would have to have at a minimum that join's type unifies with Maybe a -> a. And this is a problem, because Nothing :: Maybe a, and then join Nothing is really hard to implement!

So, wherever you are dealing with Maybes, you have to deal with the possibility that it is Nothing. This is by design, and a good thing; it stops you from cheating. So, for example, I might want to write

itemCount :: Maybe Int -> Int
itemCount = \a -> case a of
    Just n -> n
    Nothing -> 0

if I were using the Maybe to represent how many of an item was in stock or something; I have to explicitly choose how many are "in stock" when the item is not in stock. (Aside: I used your style to write that, but the idiomatic way would be

itemCount (Just n) = n
itemCount Nothing = 0

to reduce syntactic noise some.)

CodePudding user response：

join flattens always exactly two layers down to one. Ideally we would like to express something like “recursively flatten any nested layers; if we're down to one layer, don't do anything”. This would require a type like

type family Flattened x where
  Flattened (m (m a)) = Flattened (m a)
  Flattened (m a) = m a

flatten :: x -> Flattened x

Actually, this can't (AFAIK) be implemented as such though, we need some heavy machinery:

{-# LANGUAGE TypeFamilies, GADTs, ConstraintKinds
        , MultiParamTypeClasses, FlexibleInstances
        , RankNTypes, UnicodeSyntax
        , ScopedTypeVariables, AllowAmbiguousTypes, TypeApplications #-}

import Control.Monad

type family Stripped m x where
  Stripped m (m a) = Stripped m a
  Stripped m x = x

type Bare m x = Stripped m x ~ x

data DepthSing m x where
  BareSing :: Bare m x => DepthSing m x
  DeepSing :: KnownDepth m x => DepthSing m (m x)

class KnownDepth m x where
  depth :: DepthSing m x

flatten :: ∀ m x . (Monad m, KnownDepth m x) => m x -> m (Stripped m x)
flatten p = case depth @m @x of
   BareSing -> p
   DeepSing -> flatten $ join p

instance KnownDepth m Char where
  depth = BareSing

instance KnownDepth m a => KnownDepth m (m a) where
  depth = DeepSing

Now

*Main> flatten (Just (Just 'v'))
Just 'v'
*Main> flatten (Just (Just (Just 'w')))
Just 'w'
*Main> flatten (Just 'i')
Just 'i'

The awkward thing is that we need a dedicated KnownDepth instance for every “primitive” type.

instance KnownDepth m Int where depth = BareSing
instance KnownDepth m Bool where depth = BareSing
...

Perhaps -XIncoherentInstances could help, but that's an extension I'm not touching.