Алгоритм Прима для минимальных остовных деревьев


Я хочу написать статью, давая Хаскелл введение специально для Java-разработчиков, и хотели бы получить обратную связь по моей реализации. Пожалуйста, имейте в виду, что я не хочу быть "слишком умным", так как слишком сложные понятия Хаскелл будет только запутывать читателя. С другой стороны мне нужно, чтобы показать некоторые действительно интересные особенности (например, вот почему я решил использовать краю двуспальной и тип экземпляра класса вместо простого (строка, строка, двойной)), то читатели будут спрашивать "А где преимущество за Ява?". Поэтому мне нужен хороший баланс между ясностью и "интересные вещи", показывая хороший пример выразительности Хаскелла.

module Prim (
   prim,
   Edge(..)
) where

import Data.List(sort, deleteBy)
import Data.Set(member, empty, insert, singleton, Set)

data Edge a = Edge a a Double deriving (Eq, Show)

instance Ord a => Ord (Edge a) where
   compare (Edge a b c) (Edge d e f) = 
      (c, min a b, max a b) `compare` (f, min d e, max d e)

prim [] = []
prim edges = loop (sort edges) [] startSet where
   startSet = singleton (startNode edges)
   startNode ((Edge node _ _):_) = node 

loop [] solution _ = solution
loop edges solution vertices = 
   let (e,x) = findNextEdge edges vertices
       vertices' = x `insert` vertices
       cyclicEdge (Edge a b _) = a `member` vertices' && 
                                 b `member` vertices' 
       edges' = filter (not.cyclicEdge) edges 
   in loop edges' (e:solution) vertices'   

findNextEdge [] vs = error ("Disjunct graph with island " ++ show vs)                               
findNextEdge (e@(Edge a b _):edges) vertices 
    | a `member` vertices = (e,b)
    | b `member` vertices = (e,a)
    | otherwise = findNextEdge edges vertices

В частности, меня интересуют эти понятия:

  • Определение типа
  • Лень, неизменяемость
  • Карринг
  • Сопоставление с образцом, охранники
  • АДЦ и полиморфизм типа


1643
14
задан 8 июня 2011 в 08:06 Источник Поделиться
Комментарии
1 ответ


  • Java-разработчики предпочитают намерение раскрывая имена, в отличие от математических однобуквенные идентификаторы. Так что это может быть лучше использовать кромку вместо е и так далее.

  • Наиболее распространенный тип имя параметра в Java - т в отличие от гостей, поэтому, возможно, используя не менее " т " (если не нормальное имя типа), чтобы избежать путаницы и лучше объяснить АДЦ.

  • цикл может выглядеть как синтаксическая конструкция, особенно потому, что его определение следует после.

  • Просто деталь, но initialSet вместо startSet будет понятнее для меня - то же самое справедливо и для startnode приведена.

  • Я бы заменил , где с Давайте, потому что это было бы построить более менее (хотя идиоматические один) и это Конвенции в обычных языках писать заявления/определения перед использованием.

  • Я также хотел отрегулировать цикл, подпись, поэтому решение не между входными аргументами - я хотел сделать это последний аргумент.

  • Я бы не стал использовать апостроф ('), хотя я понимаю, это общепринятая в математике и теории программирования, но и среди backquoutes (`) для инфиксные операторы это может ввести в заблуждение.

  • Я думаю, что это поможет, если функция operator состава (.) был окружен пробелами - было бы лучше показать, что это разные рода '.' чем в Импорт данных.Список(сортировка, deleteBy), что может быть легче понять, для Java разработчиков.

Я не гуру Haskell и у меня нет 10+ лет опыта работы на Java, так что принять это как личное мнение. Она также может помочь довольно много, чтобы показать то же самое реализовано в Java - преимущества особенности описать и синтаксические конструкции будет понятнее. Не стесняйтесь комментировать этот ответ, я открыт для обсуждения.

5
ответ дан 10 июля 2011 в 08:07 Источник Поделиться