Линеаризация списка функций — SWI Prolog

Программирование Помощь с решением задач на Prolog Задачи на списки Линеаризация списка функций — SWI Prolog

В этой теме 5 ответов, 2 участника, последнее обновление  Васильев Владимир Сергеевич 3 года/лет, 8 мес. назад.

Просмотр 6 сообщений - с 1 по 6 (из 6 всего)
  • Автор
    Сообщения
  • #1740

    questioner
    Участник

    Здравствуйте!
    Помогите, пожалуйста, разобраться.
    На SWI-Prolog мне нужно линеаризировать список(структуру) и удалить оттуда головы вложенных списков. Иными словами, на вход подается структура вида:
    f (a, f1(b,c), f2( d, f3(e) ) )
    В процессе должен получиться список вида [f,a,[f1,b,c], [f2,d,[f3[e]]] ] , из которого мне нужно удалить головы f,f1,f2,f3 и выдать на выходе [a,b,c,d,e].
    Подскажите, пожалуйста, как лучше сделать, сначала линеаризировать, потом разбить на голову и хвост, далее с помощью append вычесть из всего списка эти головы или удалять их через delete? Или сначала разбивать на головы и хвосты и потом линеаризировать? Мне не очень понятно, как из структуры сделать список, если на вход мне подаются именно круглые скобки, а не квадратные, как у списка.
    Растолкуйте, пожалуйста.

    #1741

    В SWI Prolog есть чудный оператор «=..», который надо использовать в твоей задаче (с ним она решается более чем тривиально).
    Оператор этот, преобразует список в функцию {функцию потом можно вызвать предикатом call}. Первым аргументом списка должно идти имя функции. Например список [f, g, h] он превратит в f(g, h).

    ?- X =.. [f, g, h].
    X = f(g, h).

    Но можно сделать и обратное действие, если поменять аргументы местами:

    ?- f(g, h) =.. X.
    X = [f, g, h].

    Но, именно это тебе и требуется, вроде бы.
    После первого применения этого оператора к функции твоего примера, картина будет такой:

    ?- f(a, f1(b,c), f2( d, f3(e))) =.. X.
    X = [f, a, f1(b, c), f2(d, f3(e))].

    Очевидно, тебе нужна штука, которая обходит список, ищет в нем функции (скорее всего поможет стандартный предикат callable), применяет к ним оператор «=..» и обрабатывает рекурсивно результат.

    #1742

    questioner
    Участник

    Действительно, чудесный оператор «=..», спасибо большое!
    Только разъясните, пожалуйста, про call и callable. Мной было найдено следующее:

    all(Goal) выполняет Goal. call/1 выполняется успешно если Goal предоставляет запрос, являющийся истиной

    Я пытаюсь сделать следующее, поправьте, пожалуйста.

    struc(L,Y):- 
      L =.. Y, dev(Y).
    dev([]).
    dev([H|T]):- 
      write(H), remove([H|T],H,T), 
      write(T), struc(T,Y) .
     
    remove( [H|T],H,[H|R]):-
      remove( T, H, R ),!.

    #1743

    Не понял я почему должен получиться именно такой список (особенно, почему там [e] написано).
    Вот такой код решает вашу задачу:

    f_to_list([], []):-!.
    f_to_list([H|T], R):-
      H =.. L, length(L, Len), Len > 1, !, f_to_list(L, LR), f_to_list(T, TR), R = [LR|TR];
      f_to_list(T, TR), R = [H|TR].

    callable не помог. Я ошибся. Мы преобразуем функтор в список оператором «=..», а затем проверяем наличие аргументов. Если длина списка больше 1 — то аргументы есть, иначе — их нет. Если аргументы есть — надо их рекурсивно обработать.

    Пример вызова:

    ?- f_to_list([f(a, f1(b,c), f2(d, f3(e)))], [R]), write(R).
    [f,a,[f1,b,c],[f2,d,[f3,e]]]
    R = [f, a, [f1, b, c], [f2, d, [f3, e]]].

    Удалить первые элементы всех вложенных списков может такое правило:

    rem_heads([], []):-!.
    rem_heads([H|T], R):-
        is_list(H), !, H = [_|HT], rem_heads(HT, HTR), rem_heads(T, TR), R = [HTR|TR];
        rem_heads(T, TR), R = [H|TR].

    Для твоего примера я вызывал его следующим образом:

    ?- f_to_list([f(a, f1(b,c), f2(d, f3(e)))], L), rem_heads(L, R), write(L), nl, write(R), nl.
    [[f,a,[f1,b,c],[f2,d,[f3,e]]]]
    [[a,[b,c],[d,[e]]]]

    Линеаризовать результат может предикат flatten (стандартный):

    ?- f_to_list([f(a, f1(b,c), f2(d, f3(e)))], L), rem_heads(L, R), flatten(R, FR).
    L = [[f, a, [f1, b, c], [f2, d, [f3|...]]]],
    R = [[a, [b, c], [d, [e]]]],
    FR = [a, b, c, d, e].

    #1744

    questioner
    Участник

    Не могли бы Вы пояснить, пожалуйста, как именно работает правило rem_heads? Как именно он идет по вложенным спискам и как вообще по ним ходить?
    И еще один вопрос, как найти количество списков и вложенных в него списков заданной длины (заданного количества элементов в списке/вложенном списке). Помогите, пожалуйста!

    #1745

    % если исходный список пустой, то результат - пустой список
    rem_heads([], []):-!.
    % из непустого списка отделяется первый элемент (H), остается хвост(T)
    rem_heads([H|T], R):-
    % если H - тоже список (вложенный) - то:
    % от него отбрасывается первый элемент, остается HT
    % рекурсивно обрабатывается HT
    % рекурсивно обрабатывается T
    % результаты соединяются
        is_list(H), !, H = [_|HT], rem_heads(HT, HTR), rem_heads(T, TR), R = [HTR|TR];
    % если же H - не список - то первый элемент выкидывать не требуется
    % поэтому просто рекурсивно обрабатываем T, получаем TR
    % и для получения результата приделаем к этому TR наш H
        rem_heads(T, TR), R = [H|TR].

Просмотр 6 сообщений - с 1 по 6 (из 6 всего)

Для ответа в этой теме необходимо авторизоваться.