Reading String data into a Tree like nested grid structure (like Sudoku Board)

Question

Context

The original idea is to create an efficient grid structure for a Sudoku like board but this can be applied to many such grid structures (like wavelet transform on images, JPEG2000 etc). This particular one is basically a 9x9 Board which is made up of 3x3 Blocks where each Block is made up of 3 x Axis a a a type. You may think Axis type like a list limited to having only 3 elements (no more no less) and no empty or identiy element.

I have defined the Axis, Block and Board types as;

data Axis a =  Axis { _0 :: a
                    , _1 :: a
                    , _2 :: a
                    } deriving (Eq, Functor)
type Block a = (Axis(Axis a))
type Board a = (Axis(Axis (Block a)))

instance Show a => Show (Axis a) where
  showsPrec _ (Axis x y z) = shows x . (' ':) . shows y . (' ':) . shows z

As you notice, polymorphic Axis type is like a ternary tree with no leaves where the nodes can either be another Axis a type or an a type value. Does anybody know a general name for such data types in Haskell literature?

Anyways, by doing so, once i have a Board then i can easily access any Block or Cell quite efficiently. To access one of the 9 Blocks i can now simply do

_0 . _1 $ myBoard -- like (row 0, col 1) from myBoard

where to gain access to any cell within the Board all i have to do is to get to the Block and then to the cell like

_2 . _1 . _0 . _1 $ myBoard --  coord of cell . coord of Block => (_2 . _1) . (_0 . _1)

Problem

The problem arose when building up my Board type from a provided String. Since i post this here, I have done it but it smells like a fish and i think there must be a better way.

So the input data comes in the form of a string of 81 numeric characters among 0..9. The string should fill up the board line by line. So if my board supposed to be a 2D list, then a chunksOf 9 . map ((read :: String-> Int) . pure) would be sufficient. However the Board type is a 4 fold nested Axis type.

To start with, I couldn't even find a way to write a Read instance for the Board type at all. My solution is to first convert the flat list into a nested list of proper structure like.

nestList :: [a] -> [[[[a]]]]
nestList = map transpose . chunksOf 3 . chunksOf 3 . chunksOf 3

and then after a 2 days war with GHC infinite type errors and whatnot, i could finally come up with this stinky part.

axify :: [[[[a]]]] -> Board a
axify ([a,b,c]) = Axis (Axis (axify' $ a !! 0) (axify' $ a !! 1) (axify' $ a !! 2))
                       (Axis (axify' $ b !! 0) (axify' $ b !! 1) (axify' $ b !! 2))
                       (Axis (axify' $ c !! 0) (axify' $ c !! 1) (axify' $ c !! 2))
                  where
                  axify' ([a,b,c]) = Axis (Axis (a !! 0) (a !! 1) (a !! 2))
                                          (Axis (b !! 0) (b !! 1) (b !! 2))
                                          (Axis (c !! 0) (c !! 1) (c !! 2))

Now this works. I can fill the Board properly from a flat string and the Show instance just gives back a stringified version of the nestedList.

Question

Could anybody please help me with a proper Read instance or at least an axify function that is idiomatic (generalized to n fold Axis a type)?

Many thanks in advance.

Answer 1

Consider the polymorphic function:

axis :: [a] -> Axis a
axis [x,y,z] = Axis x y z

You want to apply this at each of the four "list levels" of the output [[[[a]]]] of nestList. So, if you have:

lst4 : [[[[Char]]]]
lst4 = nestList "295743861431865927876192543387459216612387495549216738763534189928671354154938672"

you want to write:

axis lst4 :: Axis [[[Char]]]

to replace the outermost list with an Axis, then you want to fmap axis over the Axis:

fmap axis . axis $ lst4 :: Axis (Axis [[Char]])

to replace the second-level list with an Axis, then you want to do a double-fmap (fmap axis):

fmap (fmap axis) . fmap axis . axis $ lst4 :: Axis (Axis (Axis [Char]))

to replace the third-level list, and finally the innermost list:

fmap (fmap (fmap axis)) . fmap (fmap axis) . fmap axis . axis $ lst4 :: Axis (Axis (Axis (Axis Char)))

So, you actually have:

axify :: [[[[a]]]] -> Board a
axify = fmap (fmap (fmap axis)) . fmap (fmap axis) . fmap axis . axis

Alternatively, instead of using the functor instance for Axis, you could use the functor instance for lists, starting from the inside out:

axify = axis . map axis . map (map axis) . map (map (map axis))

Answer 2

@K. A. Buhr's answer is good but eventhough i have accepted, it is very tailored to a single problem. A more generalized one would be more idiomatic alas dealing with such nested data structures in Haskell quickly take you into many rabbit holes. Think about flattening an indefinitelly nested list with a recursive function. We have a similar problem at hand here.

As it turns out, we can do it without getting our hands wet with dependent types and type famillies etc. So here I am answering my own question starting with a little prologue.

Prologue

When I started with Haskell the most intimidating part happened to be (still is) the Language extensions. To start with there are so many of them. While some are very straightforward, some have the potentital to turn the language into a signifcantly different one. When you study them through some tutorials you are forced to walk on a specific case of authors choice. Most of the time i can not even tell which one to apply for a particular need of mine. Just like in this case.

Let's get started. As always most of the time, deep inside, at the dark corners of SO there are gem like answers. For this particular case my starting point was Is there a function to flatten a nested list of elements? This answer is old but really bears the answer to many similar problems. Deserves upvoting :)

Solution

We best start with a new type class which will be the home of the axify function. This particular type class definition will be unusual though. We will constrain it both with the input (i) and the output (o) types, well type parameters. So 2 type parameters and 1 type class => {-# LANGUAGE MultiParamTypeClasses #-}.

class Axable i o where
  axify :: [i] -> Axis o

So axify function takes a list of i types and gives an Axis o type. axify also is a recursive function. So we need a base case for termination. If we think about the simplest case of axify [1,2,3] == Axis 1 2 3. We notice that both i and o are of the same type which is Int. This base case deserves an instance of it's own.

instance Axable a a where
  axify [a,b,c] = Axis a b c

Now how about having a nested list to axify at hand?

instance Axable i o => Axable [i] (Axis o) where
  axify [as,bs,cs] = Axis (axify as) (axify bs) (axify cs)

which says, given both i and o are of Axable class, we define an instance for the case when the input is of [i] and the output is of Axis o types.

:r and

• Illegal instance declaration for ‘Axable a a’
    (All instance types must be of the form (T a1 ... an)
     where a1 ... an are *distinct type variables*,
     and each type variable appears at most once in the instance head.
     Use FlexibleInstances if you want to disable this.)

Ok throw a {-# LANGUAGE FlexibleInstances #-} in the mix to see Ok, one module loaded.

ts = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81"
nestList :: String -> [[[[Int]]]]
nestList = map transpose . chunksOf 3 . chunksOf 3 . chunksOf 3 . map read . words

λ> axify (nestList ts) :: Board Int
1 2 3 10 11 12 19 20 21 4 5 6 13 14 15 22 23 24 7 8 9 16 17 18 25 26 27 28 29 30 37 38 39 46 47 48 31 32 33 40 41 42 49 50 51 34 35 36 43 44 45 52 53 54 55 56 57 64 65 66 73 74 75 58 59 60 67 68 69 76 77 78 61 62 63 70 71 72 79 80 81

Epilogue

The above answer in SO uses the OverlappingInstances language extension which is depreciated in the favor of the new instance only pragmas {-# OVERLAPPING #-}, {-# OVERLAPPABLE #-}, {-# OVERLAPS #-}, or {-# INCOHERENT #-}. So i was getting prepared to use one of them but it seems nothing is overlapping here. Now of course we shall consider embedding the nesting functionality nestList into axify as well but that's a relatively trivial job which is out of the concerns of this topic.

Answer 3

You can use recursive type class to parse arbitrarily nested axes.

instance Read a => Read (Axis a) where
  readsPrec n str = do
    (a, str) <- readsPrec n str
    (b, str) <- readsPrec n str
    (c, str) <- readsPrec n str
    return (Axis a b c, str)

Now you can

read $ unwords $ map show [1..3^2] :: Axis (Axis Int)
read $ unwords $ map show [1..3^3] :: Axis (Axis (Axis Int))
read $ unwords $ map show [1..3^4] :: Axis (Axis (Axis (Axis Int)))
...

---

It is handy to use associated type synonyms to implement axify:

{-# LANGUAGE TypeFamilies #-}

class Axify a where
  type Res a
  axify :: a -> Res a

instance Axify Int where
  type Res Int = Int
  axify a = a

instance Axify a => Axify [a] where
  type Res [a] = Axis (Res a)
  axify [a,b,c] = Axis (axify a) (axify b) (axify c)

-- axify [1,2,3::Int] :: Axis Int
-- axify [[1,2,3], [4,5,6], [7,8,9::Int]] :: Axis (Axis Int)

Actually this is the same approach as in your own answer (with MultiParamClassTypes) but a bit more robust as associated types establish one-to-one correspondence between [a] and Axis a.

This allows type checker to infer more types. E.g.

axify [1,2,3::Int]

typechecks with associated types but requires additional type signature with multiparam type class.