Как избавиться от скобок в Haskell'е?

Question

[Аня Коломенская]

Вот мой код на Haskell'е:

infixl 6 :$:
data ExE  =  ExData Integer | ExE :$: ExE deriving (Show, Eq)

simplify                       :: ExE -> ExE
simplify ((a1 :$: a2) :$: a3)  =  simplify a1 :$: simplify a2 :$: simplify a3
simplify (a1 :$: (a2 :$: a3))  =  simplify a1 :$: simplify a2 :$: simplify a3
simplify (a1 :$: a2)           =  simplify a1 :$: simplify a2
simplify a                     =  a

Вот результат его работы:

*ExTesting> simplify $ (ExData 1 :$: ExData 2) :$: ExData 3
(ExData 1 :$: ExData 2) :$: ExData 3
*ExTesting> simplify $ ExData 1 :$: (ExData 2 :$: ExData 3)
(ExData 1 :$: ExData 2) :$: ExData 3

Тогда как надо было получить это:

*ExTesting> simplify $ (ExData 1 :$: ExData 2) :$: ExData 3
ExData 1 :$: ExData 2 :$: ExData 3
*ExTesting> simplify $ ExData 1 :$: (ExData 2 :$: ExData 3)
ExData 1 :$: ExData 2 :$: ExData 3

Как мне избавиться от этих лишних скобок в результате?

Answer 1

[Василий Дёмин]

Можно вручную определить show для ExE.

instance Show ExE where
  show exe = case exe of
      ExData i -> "ExData " ++ show i
      e1 :$: e2 -> show e1 ++ " :$: " ++ show e2

Comments

[Александр Скуснов]

Видно, стандартный подход поясняет левую ассоциативность.

[Аня Коломенская]

Василий Дёмин.
Верно, такое решение напрашивается само - я бы так и сделала, если бы это подходило. Но это я здесь просто вывожу результат сразу, тогда как на самом деле эта функция будет использоваться внутри других функций, которые используются внутри других функций... ну и так далее. Поэтому задача в том, чтобы именно убрать скобки непосредственно из результата функции, а не в show. И я всё ещё не понимаю, как это сделать.

Александр Скуснов.
Да, именно так и есть. Я понимаю, откуда там скобки, но не соображу, как от них избавиться.

[Василий Дёмин]

Аня Коломенская, Что значит убрать скобки из результата? Я правильно понимаю, что вы хотите из ((a :$: b) :$: c) сделать a :$: b :$: c во внутреннем представлении? Если так, то это невозможно.

[wiz]

Можно только сменить круглые скобки на квадратные если собрать все аргументы в список.

[Аня Коломенская]

Василий Дёмин, Я поняла это и поэтому послала Haskell к чертям. Но спасибо - тогда я действительно искала решение.

[Василий Дёмин]

Аня Коломенская, Это не особенность конкретно haskell. На любом другом языке синтаксическое дерево бинарных операторов также будет либо неассоциативно, либо левоассоциативно, либо правоассоциативно. Чтобы не быть голословным приведу пример на си, в котором выражение 1 :$: 2 :$: 3 представлено левоассоциативным и правоассоциативным с помощью одной структуры ExE.

#include <stdio.h>
#include <stdbool.h>

typedef struct ExE {
    bool isLeaf;
    union {
        struct {
            struct ExE *left;
            struct ExE *right;
        };
        int exdata;
    };
} ExE;

void printNode(ExE *node) {
    if(node->isLeaf) {
        printf("ExData %d", node->exdata);
    } else {
        putchar('(');
        printNode(node->left);
        printf(" :$: ");
        printNode(node->right);
        putchar(')');
    }
}

void printExE(ExE *root) {
    printNode(root);
    putchar('\n');
}

int main() {
    ExE leaf3 = {
        .isLeaf = true,
        .exdata = 3,
    };

    ExE leaf2 = {
        .isLeaf = true,
        .exdata = 2,
    };

    ExE leaf1 = {
        .isLeaf = true,
        .exdata = 1,
    };

    // 1 :$: (2 :$: 3)
    ExE rNode1 = {
        .isLeaf = false,
        .left   = &leaf2,
        .right  = &leaf3,
    };

    ExE rRoot = {
        .isLeaf = false,
        .left   = &leaf1,
        .right  = &rNode1,
    };
    printExE(&rRoot);

    // (1 :$: 2) :$: 3
    ExE lNode1 = {
        .isLeaf = false,
        .left   = &leaf1,
        .right  = &leaf2,
    };

    ExE lRoot = {
        .isLeaf = false,
        .left   = &lNode1,
        .right  = &leaf3,
    };
    printExE(&lRoot);
}

В первом случае printExE выведет: (ExData 1 :$: (ExData 2 :$: ExData 3)).
Во втором - ((ExData 1 :$: ExData 2) :$: ExData 3)

[Василий Дёмин]

Аня Коломенская, Что вы хотите сделать такого, что для этого нужно убрать скобки? Мне кажется это можно сделать и без убирания скобок.

[Аня Коломенская]

Василий Дёмин, Конкретно там всё же нужно было, чтобы просто не было скобок. Ассоциативности это напрямую не касается, так как, например, в математике
y = a*x^3 + b*x^2 + c*x + d
будет тем же самым, что и
y = a*x^3 + (b*x^2 + (c*x + d))
Ну или пример с операцией, где порядок важен:
y = x^x^2 и y = x^(x^2)
Возвращаясь к задаче - вот по этому же принципу лишние скобки нужно было удалить из выражения. То есть если выражение не рушится после удаления скобок, их нужно убрать. Но Haskell упорно сам ставил эти скобки, хотя как раз с учётом ассоциативности скобки там были лишними. (Я пыталась написать парсер математических выражений с функцией их автоматического упрощения).

[Василий Дёмин]

Аня Коломенская, На haskell можно написать программу, упрощающую математические выражения. В качестве примера могу скинуть данный репозиторий, т.к. код в нём достаточно прост: https://github.com/AndoBando/NibHs. Haskell никакие скобки никуда не вставляет, как я писал выше, отображение скобок в show связано только со структурой хранения выражений. Для скобок в математических выражениях можно создать отдельный конструктор и использовать его, например так:

data Expr a = Var String
            | (Expr a) :$: (Expr a)
            | Parens (Expr a)

Теперь можно считать, что всё, что не в конструкторе Parens, является выражением без скобок.