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

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. ## 3 Answers 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))

• Thank you for your time. That's soo much better. i can't help questioning though.. what would be the proper approach in Haskell to axify into an indefinite depth..? Since axify can not be made recursive, should one look into dependent types or type families or perhaps comonads. I am quite lost there. I was reading this and this. – Redu May 16 '20 at 6:28
• That would make a very good Stack Overflow question, particularly if you could give a simplified example that illustrates exactly how you'd want axify to behave. For example, are you maybe looking for something like axify 1 ["foo","bar",zip"] = Axis "foo" "bar" "zip" vs. axify 2 ["foo","bar","zip"] = Axis (Axis "f" "o" "o", Axis "b" "a" "r", Axis "z" "i" "p")? – K. A. Buhr May 16 '20 at 19:10
• So in other words you say, "Find a new data type for nested lists bearing the depth in the first place" such that the type signature for nesrList would become like nestList :: [a] -> Nested a whereas data Nested a = Nested Int [Nested a] perhaps or stg. I feel this quest might require a whole new library. :) I will think about it. – Redu May 16 '20 at 20:15

@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.

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.

• Thank you. This is great Read instance which earns an upvote but it's only a half measure. It's fine in nesting the Axis Int type from a String but the Board Int ~ Axis (Axis (Axis (Axis Int))) gets populated incorrectly. The point of nestList function is to put the input String into such a nested structure that will yield a correct axifying process. I mean the first Block Int would be Axis (Axis 1 2 3) (Axis 10 11 12) (Axis 19 20 21) not Axis (Axis 1 2 3) (Axis 4 5 6) (Axis 7 8 9). – Redu May 19 '20 at 15:08
• Thank you for extending your answer. This might form a reasonable exercise for me to step into type families. – Redu May 19 '20 at 15:35