1. Haskell / Говнокод #22737

    −100

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    topSort :: V.Vector ([Int], [Int])
           -> Either String [Int]
    topSort kob =
      let
        sup u k = do
          let max i = (i,) . head . snd <$> k `MV.read` i
          l <- mapM max u
          case filter (uncurry (==)) l of
            [(a,_)] -> return $ Right a
            x -> return $ Left "Topology error"
    
        rewrite k s (i, j) = do
          let f x | x == s && j < 0 = []
                  | x == s = [j]
                  | otherwise = [x]
          when (j>=0) $ MV.modify k (_1 %~ (i:)) j
          MV.modify k (_2 %~ (>>= f)) i
    
        go u k =
          readSTRef u >>= \case
            [a] -> return $ Right [a]
            u_ -> sup u_ k >>= \case
              Right s -> do
                modifySTRef' u $ Data.List.delete s
                s_d <- fst <$> MV.read k s
                mapM_ (rewrite k s) $ zip s_d (tail s_d ++ [-1])
                tail <- go u k
                return $ (s:) <$> tail
              Left err ->
                return  $ Left err
    
      in runST $ do
        u <- newSTRef $ [0..V.length kob-1]
        k <- V.thaw kob
        liftM reverse <$> go u k

    Пишем на декларативном языке

    Запостил: CHayT, 04 Апреля 2017

    Комментарии (7) RSS

    • seo-post: о преимуществах функциональной парадигмы перед императивной
      Ответить
    • Если бы не название функции, я бы не догадался, что тут происходит. Где ты это откопал?

      Я так понимаю, u — это список(sic!) ещё не посещённых вершин. Не понятно только, зачем нужен медленный список внутри мутабельной переменной, когда гораздо проще использовать мутабельный массив, как это делается в Data.Graph?

      > Either String
      тоже забавно, stringly typed programming

      Ну и import Data.Graph (topSort), разумеется.
      Ответить
      • > Где ты это откопал?
        Сам высрал как прототип. Во время бессонницы, скажу в оправдание.
        > Не понятно только, зачем нужен медленный список внутри мутабельной переменной, когда гораздо проще использовать мутабельный массив, как это делается в Data.Graph?
        В основном потому что этот код мутировал из иммутабельного.
        > import Data.Graph (topSort)
        Это не просто граф, т.к. входные данные несут не только инвормацию о рёбрах, но ещё и об относительном порядке в результирующем массиве. Обычный топсорт её проебёт.
        Ответить
        • > Обычный топсорт её проебёт
          Используй алгоритм Kahn-а вместо dfs, он может выдавать лексикографически-минимальную топологическую сортировку.
          Ответить
        • Вот так примерно выглядит императивный Kahn на псевдокоде (писал на коленке, могут быть косяки, но идея должна быть ясна):
          def toposort(Graph G(V, E)):
            Vect<Vertex> out_degree(0, |V|);
            Vect<Vertex> toposort;
            Heap<Vertex> heap(CompareAsYouLike);
          
            foreach (from, to) in E {
              out_degree[from]++;
            }
          
            foreach v in V {
              if out_degree[v] == 0 {
                heap.push(v);
              }
            }
          
            while !heap.empty() {
              Vertex v = heap.extract_min();
              toposort.push(v);
              foreach (from, to) in incoming_edges(G, v) {
                out_degree[from] -= 1;
          
                if out_degree[from] == 0 {
                  heap.push(from);
                }
              }
            }
          
            if toposort.size() != |V| {
              raise TopologyError;
            }
          
            return toposort;
          }
          Как видишь, для эффективности нужно иметь ещё и инвертированный граф, чтобы быстро находить рёбра, входящие в вершину ("incoming_edges(G, v)").
          Ответить
          • У меня роль играет, в каком именно порядке рёбра определены в _каждой_ вершине, так что это не просто некий граф, а более информативная кобенация, которую можно было бы представить и обычным графом, но гораздо большего размера.
            Ответить
            • А что это меняет? Слишком сложно будет посчитать отношение порядка между вершинами?
              Ответить

    Добавить комментарий