Что такое эквивалент self.val в функциональном программировании? - PullRequest
Новая
       304

Что такое эквивалент self.val в функциональном программировании?

0 голосов
/ 14 июня 2019

Если мы программируем oop способом, нам предоставляется гибкость для self.var 

class Solution:
    def isValidBST(self, root):
        self.lastVal = - 2**32 
        self.isBST = True
        self.valid(root)
        return self.isBST

    def valid(self, node): # in-order traversal
        if node is None:
            return

        self.valid(node.left)
        if self.lastVal >= node.val:
            self.isBST = None
            return
        self.lastVal = node.val
        self.valid(node.right)

Но если мы программируем функциональным способом: 

def isBST(root):
   is_bst = True
   last_val = -2 ** 32

  def valid(node):
    if node == None:
        return 
    valid(node.left)

    if node.val <= last_val:
        is_bst = False
        return
    last_val = node.val
    valid(node.right)

  valid(root)
  return is_bst

, мы встретимся с проблемой:

локальная переменная 'last_val', на которую ссылаются перед присваиванием.

Есть ли способ использовать гибкость self.var в функциональном программировании на Python?

Ответы [ 2 ]

1 голос
/ 15 июня 2019

Переменные экземпляра похожи на ограниченную форму глобальной переменной. Каждый экземпляр можно рассматривать как автономную (предназначенную для каламбура) область, которая передается как явный аргумент функции. Без класса вы бы просто передавали каждую общую переменную явно, а не неявно, как часть аргумента self. 

def isValidBST(root, lastVal, isBST):
    lastVal = - 2**32 
    self.isBST = True
    lastVal, isBST = valid(root, lastVal, isBST)
    return lastVal, isBST

def valid(node, lastVal, isBST):
    if node is None:
        return lastVal, isBST

    lastVal, isBST = valid(node.left, lastVal, isBST)
    if lastVal >= node.val:
        isBST = None
        return lastVal, isBST

    lastVal = node.val
    lastVal, isBST = valid(node.right, lastVal, isBST)
    return lastVal, isBST

Ясно, что в приведенном выше описании есть место для упрощения: isValidBST на самом деле не нужно принимать дополнительные аргументы, поскольку он игнорирует их и устанавливает их явно; вы можете просто использовать return valid(root, lastVal, isBST) вместо распаковки возвращаемого значения и повторной упаковки для возврата значений; и т.д. Но идея есть: глобальные переменные могут быть заменены явными аргументами функции и возвращаемыми значениями.

Если вы изучите такой язык, как Haskell, вы обнаружите монаду State, которая является способом абстрагирования повторения передачи глобального состояния таким образом и написания кода, который «выглядит» так, как будто он использует глобальные переменные .

1 голос
/ 15 июня 2019

Вы можете обойтись без класса Solution, но древовидная структура данных по-прежнему должна существовать.Учитывая, что вы не создаете его в коде, который вы даете, я предполагаю, что это уже сделано.

Так что вот функциональное решение more (в том, что его возвращаемое значение является тем, что важно, иу него нет внешнего состояния): 

def isBST(node, minVal=-2**32, maxVal=2**32):
    if node is None:
        # recursive base case.
        return True
    # ensure that this node has an appropriate value
    if node.val <= minVal or node.val > maxVal:
        return False
    # ensure that this node's children have appropriate values
    return isBST(node.left, minVal, node.val) and isBST(node.right, node.val, maxVal)

(как примечание, я извлек этот алгоритм из wikipedia , потому что мне было лень самому в этом разобраться).

Вы не можете реализовать это должным образом без включения minVal и maxVal в качестве параметров - но мы можем установить значения по умолчанию для них, когда мы определим функцию, и в результате вы все равно можете сделать isBST(root) иэто будет прекрасно работать.И это нормально в функциональном программировании для функции, имеющей несколько входов, подобных этой.

...