Разделить список на положительные, отрицательные и нулевый элементы

      Комментарии к записи Разделить список на положительные, отрицательные и нулевый элементы отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Разделить список на положительные, отрицательные и нулевый элементы

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

  • Автор
    Сообщения
  • #2286

    questioner
    Участник

    Здравствуйте, нужна функция выделения из списка отрицательных, положительных и нулевых элементов — в результате должны формироваться три списка, например:

    divide_positive_negative_zero([1,2,-4,-5,0],Positive,Negative,Zero).
    Positive = [1, 2],
    Negative = [-4, -5],
    Zero = [0] 

    Я написал следующий код:
    divide_positive_negative_zero([Head|Tail],[Head|TailPostive],Negative,Zero):-
            Head>0,
            divide_positive_negative_zero(Tail,TailPostive,Negative,Zero).
    divide_positive_negative_zero([Head|Tail],Postive,[Head|TailNegative],Zero):-
            Head<0,
            divide_positive_negative_zero(Tail,Postive,TailNegative,Zero).
    divide_positive_negative_zero([Head|Tail],Postive,Negative,[Head|TailZero]):-
            Head=0,
            divide_positive_negative_zero(Tail,Postive,Negative,TailZero).
    divide_positive_negative_zero([],[],[],[]).

    Тут элементы последовательно выбираются из исходного списка и сравниваются с нулем. Остальные элементы списка обрабатываются рекурсивно — в результате формируется три списка. В зависимости от результата сравнения первый элемент списка добавляется к одному из них.
    Возможно ли его упростить?

  • #2287

    У Вас выполняется одна лишняя проверка, т.к. если в списке есть первый элемент (список не пуст), который не является положительным или отрицательным, то он однозначно является нулевым. Однако, убрать проверку просто так нельзя, т.к. при этом интерпретатор будет искать в этом правиле другие решения для случая, когда элемент является положительным, например (предикат не является детерминированным). Проблему можно решить за счет использования отсечения.
    Кроме того, можно изменить порядок правил так, чтобы проверка на ноль была не последней — тогда вместо сравнения можно использовать механизм сопоставления с образцом.

    Применение отсечения в данном случае повысит эффективность правила, т.к. рекурсивные вызовы станут хвостовыми, а значит при оптимизации кода будут заменены длинными переходами.

    divide_positive_negative_zero([Head|Tail],[Head|TailPostive],Negative,Zero):-
      Head>0,!,
      divide_positive_negative_zero(Tail,TailPostive,Negative,Zero).
    divide_positive_negative_zero([0|Tail],Postive,Negative,[0|TailZero]):-
      !,divide_positive_negative_zero(Tail,Postive,Negative,TailZero).
    divide_positive_negative_zero([Head|Tail],Postive,[Head|TailNegative],Zero):-
      divide_positive_negative_zero(Tail,Postive,TailNegative,Zero).
    divide_positive_negative_zero([],[],[],[]).

    В диалектах пролога, соответствующих международному стандарту (ISO) есть встроенная функция include, позволяющая выбрать из списка элементы, соответствующие некоторому правилу. В качестве правила при этом можно передавать либо функцию, выполняющую сравнение числа с нулем, либо лямбду, либо оператор сравнения с заданным первым аргументом. В последнем случае используется механизм каррирования:

    divide_positive_negative_zero(List, Postive, Negative, Zero):-
      include(<(0), List, Postive),
      include(>(0), List, Negative),
      include(=(0), List, Zero).

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