# Implementing the "Laws of Form" with an algebraic data type

**URL:** <https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184>\
**Category:** Learn\
**Created:** [August 17, 2024, 8:11pm UTC](https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184 "2024-08-17T20:11:19Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![TheoH](https://avatars.discourse-cdn.com/v4/letter/t/9de0a6/32.png) [@TheoH](https://discourse.haskell.org/u/TheoH)\
**Post date:** [August 17, 2024, 8:11pm UTC](https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184/1 "2024-08-17T20:11:19Z")

</div>

I have been reading a little bit about the so-called [Laws of Form](https://en.wikipedia.org/wiki/Laws_of_Form). [Dan Piponi has a complicated post with Haskell code](http://blog.sigfpe.com/2006/06/laws-of-form-opinion.html) from several years ago.

My investigations are much more basic. I’ve got a reduction algorithm working that uses the fact that the elements of lof are like a Dyck language, so strings of parentheses will work as a representation.

```haskell
test1 = "(()())"
test2 = "((()))"
test3 = "()()"

fix f x = let x' = f x in if x == x' then x else fix f x'

reduce :: String -> String
reduce ('(':')':'(':')':rest) = "()" ++ reduce rest
reduce ('(':'(':')':')':rest) = reduce rest
reduce (head:rest) = head:reduce rest
reduce [] = []

fr = fix reduce

```

In other words, at the innermost level, occurrences of (()) disappear, and occurrences of ()() become (), and this continues until you have either “” or “()” left.

This seems to work fine, but what I’m wondering is how to define the same algorithm using an algebraic data type. I’ve tried things like

```haskell
data Form = Empty | Mark [Form]

```

but writing nested values of that type gets confusing. and writing the reduce function is even more confusing. I wonder if there is a simple implementation that I am missing.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [August 17, 2024, 8:20pm UTC](https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184/2 "2024-08-17T20:20:01Z")

</div>

I think I’d write it like this:

```haskell
data Form = Mark [Form] deriving (Show, Eq)

test1 = [Mark[Mark[], Mark[]]]
test2 = [Mark[Mark[Mark[]]]]
test3 = [Mark[],Mark[]]

fix f x = let x' = f x in if x == x' then x else fix f x'

reduce :: [Form] -> [Form]
reduce (Mark[]:Mark[]:rest) = Mark[] : reduce rest
reduce (Mark[Mark[]]:rest) = reduce rest
reduce (Mark xs:rest) = Mark (reduce xs):reduce rest
reduce [] = []

fr = fix reduce

```

I’m not sure if that does exactly what you want.

---

<div class="post-metadata">

**Author:** ![TheoH](https://avatars.discourse-cdn.com/v4/letter/t/9de0a6/32.png) [@TheoH](https://discourse.haskell.org/u/TheoH)\
**Post date:** [August 17, 2024, 9:16pm UTC](https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184/3 "2024-08-17T21:16:05Z")

</div>

Ah, I see. That’s simple. Getting reduce to take a list of forms, not a single form, is a good trick. I’ll have to think about that a bit. Thank you!

---

<div class="post-metadata">

**Author:** ![darkxero](https://avatars.discourse-cdn.com/v4/letter/d/f07891/32.png) [@darkxero](https://discourse.haskell.org/u/darkxero)\
**Post date:** [August 17, 2024, 10:23pm UTC](https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184/4 "2024-08-17T22:23:28Z")

</div>

> [@TheoH](#):
>
> This seems to work fine, but what I’m wondering is how to define the same algorithm using an algebraic data type.

```haskell

data Form = Empty | One | Pairs Form Form | Wraps Form

instance Show Form where
    show form = case form of
        Empty -> ""
        One -> "()"
        Pairs f1 f2 -> show f1 ++ show f2
        Wraps f1 -> "(" ++ show f1 ++ ")"

reduceF :: Form -> Form
reduceF form = case form of
    Empty -> Empty
    One -> One
    _ -> reduceF (reduce' form)
    where
        reduce' form' = case form' of
            Empty -> Empty
            One -> One
            Pairs One One -> One
            Pairs Empty f2 -> f2
            Pairs f1 Empty -> f1
            Pairs f1 f2 -> Pairs (reduce' f1) (reduce' f2)
            Wraps One -> Empty
            Wraps Empty -> One
            Wraps f1 -> Wraps (reduce' f1)

mytest1 = Wraps $ Pairs One One
mytest2 = Wraps $ Wraps One
mytest3 = Pairs One One

test1 = "(()())"
test2 = "((()))"
test3 = "()()"

fix f x = let x' = f x in if x == x' then x else fix f x'

reduce :: String -> String
reduce ('(':')':'(':')':rest) = "()" ++ reduce rest
reduce ('(':'(':')':')':rest) = reduce rest
reduce (head:rest) = head:reduce rest
reduce [] = []

fr = fix reduce

main = do
    print $ fr test1 ++ " - " ++ show (reduceF mytest1)
    print $ fr test2 ++ " - " ++ show (reduceF mytest2)
    print $ fr test3 ++ " - " ++ show (reduceF mytest3)

```

---

<div class="post-metadata">

**Author:** ![TheoH](https://avatars.discourse-cdn.com/v4/letter/t/9de0a6/32.png) [@TheoH](https://discourse.haskell.org/u/TheoH)\
**Post date:** [August 18, 2024, 4:41pm UTC](https://discourse.haskell.org/t/implementing-the-laws-of-form-with-an-algebraic-data-type/10184/5 "2024-08-18T16:41:30Z")

</div>

This is helpful. Thank you.

I’m not sure about the use of a Pairs constructor. After all, the data structure is basically a “rose tree”, as far as I can see.

It might be overcomplicating things to say that this is a “biased definition” of the datatype, when what is really needed is the rose tree structure.

[https://ncatlab.org/nlab/show/biased+definition](https://ncatlab.org/nlab/show/biased+definition)

Writing the reduce function for a rose tree with empty leaves should probably be the next thing I try.