Pattern Matching Symbols

#1

I’ve been playing around with Symbols lately to separate alpha characters from non-alpha like so:

class Case (lower :: Symbol) (upper :: Symbol) | lower -> upper, upper -> lower

instance caseA :: Case "a" "A"
else instance caseB :: Case "b" "B"
else instance caseC :: Case "c" "C"
...
else instance caseZ :: Case "z" "Z"

foreign import kind Specifier
foreign import data Alpha :: Symbol -> Specifier
foreign import data NonAlpha :: Symbol -> Specifier

class DetectSpecifier (head :: Symbol) (out :: Specifier) | head -> out, out -> head
instance upperLetterSpec
  :: (Case lower head) => DetectSpecifier head (Alpha head)
else instance lowerLetterSpec
  :: (Case head upper) => DetectSpecifier head (Alpha head)
else instance nonLetterSpec
  :: DetectSpecifier head (NonAlpha head)

The problem is that the instance chain of DetectSpecifier accepts neither a lower case alpha nor non-alpha (I think because it pattern-matches head with upper letters first)!

data SpecProxy (t :: Specifier) = SpecProxy

symToSpec :: ∀ sym spec.
  DetectSpecifier sym spec => SProxy sym -> SpecProxy spec
symToSpec _ = SpecProxy

workForUppercase
  -- inferred type
  :: SpecProxy (Alpha "A")
workForUppercase = symToSpec (SProxy :: _ "A")

doesNotWorkForLowercase
  -- inferred type
  :: forall t8. Case t8 "a" => SpecProxy (Alpha "a")
doesNotWorkForLowercase = symToSpec (SProxy :: _ "a")

doesNotWorkForNonAlpha
  -- inferred type
  :: forall t7. Case t7 "$" => SpecProxy (Alpha "$")
doesNotWorkForNonAlpha = symToSpec (SProxy :: _ "$")

Is there a way to get it working as expected so that
“a” will return Alpha "a"
“Z” will return Alpha "Z"
“$” will return NonAlpha "$"

?

My plan is to put these Alphas and NonAlphas into a type level List which later could be interpreted in many different ways i.e converting them into lowercase, uppercase, camelcase, etc

#2

I would be careful throwing in instance chains when they’re not necessary as they can complicate things. When I first started I would add them as it’d make the error go away until I tried things in the REPL… but really it was just hiding the real problem. In your example, Case shouldn’t require the chain as they are all non-overlapping, although it doesn’t really hurt here

Secondly, for some classes to be bidirectional, you have to split it into two classes which approach the problem from two different directions, and then combine the results in a new class.

If we look at your instances for DetectSpecifier without the fluff (constraints aren’t used for selecting instance, it seems you wrote the code assuming they were), it’s obvious it will never match the second rule as it is a duplicate of the first:

instance upperLetterSpec      :: DetectSpecifier head (Alpha head)
else instance lowerLetterSpec :: DetectSpecifier head (Alpha head)
else instance nonLetterSpec   :: DetectSpecifier head (NonAlpha head)

(I explained the following code a lot more as I was going through, but then realised you didn’t want to ALSO lowercase while converting to Alpha, so it made it a lot simpler, so the following code is a result of that. Probably easier if you just ask questions instead of me writing a guide anyway. Also realised you didn’t ask for the inverse direction explicitly, for eg in your examples, but your fundeps indicated you did want it. You could probably get away with one main class for this version if ToSpecifier was bidirectional, but that requires essentially inlining the ToLower into the instances, reducing reusability)

module Messing where

import Data.Symbol (SProxy(..))

foreign import kind Specifier
foreign import data Alpha :: Symbol -> Specifier
foreign import data NonAlpha :: Symbol -> Specifier

class ToSpecifier (a :: Symbol) (spec :: Symbol -> Specifier) | a -> spec                            
-- Only need an instance chain for the overlapping instance of the last general case
-- if you enumerated all possible characters, could remove else
instance toSpecifierA :: ToSpecifier "a" Alpha
else instance toSpecifierB :: ToSpecifier "b" Alpha
else instance toSpecifierZ :: ToSpecifier "z" Alpha
else instance toSpecifierNon :: ToSpecifier a NonAlpha

class ToLower (a :: Symbol) (lower :: Symbol) | a -> lower                            

-- Same reason here for overlapping
instance toLowerA :: ToLower "A" "a"
else instance toLowerB :: ToLower "B" "b"
else instance toLowerZ :: ToLower "Z" "z"
else instance toLowerOther :: ToLower a a

class DetectSpecifierPP (head :: Symbol) (out :: Specifier) | head -> out
instance alphaSpecPP :: 
  ( ToLower head lower
  , ToSpecifier lower spec
  ) => DetectSpecifierPP head (spec head)

class DetectSpecifierP (head :: Symbol) (out :: Specifier) | out -> head
instance alphaSpecP :: DetectSpecifierP head (Alpha head)
instance nonAlphaSpecP :: DetectSpecifierP head (NonAlpha head)

class (DetectSpecifierP head out, DetectSpecifierPP head out) <= DetectSpecifier (head :: Symbol) (out :: Specifier) | head -> out, out -> head

instance alphaSpec :: 
  ( DetectSpecifierP head out
  , DetectSpecifierPP head out
  ) => DetectSpecifier head out

data SpecProxy (t :: Specifier) = SpecProxy

symToSpec :: ∀ sym spec.
  DetectSpecifier sym spec => SProxy sym -> SpecProxy spec
symToSpec _ = SpecProxy

specToSym :: ∀ sym spec.
  DetectSpecifier sym spec => SpecProxy spec -> SProxy sym
specToSym _ = SProxy

worksForNonAlpha = symToSpec (SProxy :: _ "$")
worksForLowercase = symToSpec (SProxy :: _ "a")
workForUppercase = symToSpec (SProxy :: _ "A")

worksForNonAlphaSpec = specToSym (SpecProxy :: _ (NonAlpha "$"))
worksForLowercaseSpec = specToSym (SpecProxy :: _ (Alpha "a"))
workForUppercaseSpec = specToSym (SpecProxy :: _ (Alpha "A"))
2 Likes
#3

Thanks for the thorough explanation Joseph!

Secondly, for some classes to be bidirectional, you have to split it into two classes which approach the problem from two different directions, and then combine the results in a new class.

If we look at your instances for DetectSpecifier without the fluff (constraints aren’t used for selecting instance, it seems you wrote the code assuming they were), it’s obvious it will never match the second rule as it is a duplicate of the first:

Yes I thought “pattern-matching” with instance constraints would work even though the right hand side of => stays the same. But turns out no. That helps a lot. I learnt something today!

I was also thinking to do pattern-match by hand (again) for [a-zA-Z] for DetectSpecifier if there’s really no other solution to this problem. Turns out I have to do it eventually. I’ll try your approach first :wink:

Thanks once again!