Деление полиномов на Elm

@outoftime · Регистрация: 25.07.2009

Author24 — интернет-сервис помощи студентам

Есть функциональный язык Elm который транслируется в Javascript спасает от великого множества ошибок. Это действительно так, но это функциональный язык, а я, сколько себя помню пишу на императивных языках.

Есть полином, где $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i = \{-1, 0, 1\}$ , который я просто представляю в виде списка Int где каждый элемент это степень со знаком, который соответсвует $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i$ или отсутсвует когда $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i = 0$

Другими словами, список [-5 2 1] это полином $https://www.cyberforum.ru/cgi-bin/latex.cgi?-x^5+x^2+x$

Вопрос как это реализовать на любом языке функциональном, не используя библиотек, так как я не знаю найду ли аналоги в Elm. Есть пример реализации на C++.

Вот то что у меня есть сейчас

Код

import Html exposing (..)
import Html.Attributes exposing (..)
import Html.Events exposing (..)
import List
import String
import Char
import Tuple
import Result


main =
    beginnerProgram { model = model, view = view, update = update }



-- model


type alias Polinom =
    List Int


type alias Model =
    { nominator : Polinom
    , denominator : Polinom
    , calculate : Bool
    }


type Msg
    = InputNominator String
    | InputDenominator String
    | Calculate


model : Model
model =
    Model [] [] False


dividePolinoms : Polinom -> Polinom -> Polinom
dividePolinoms nominator denominator =
    if List.length nominator < List.length denominator then
        nominator
    else
        denominator



-- views


printPolinomMember : Int -> Html Msg
printPolinomMember member =
    let
        sign =
            if member >= 0 then
                "+"
            else
                "-"
    in
        span []
            [ text <| sign ++ "x"
            , sup [] [ text <| toString <| abs member ]
            ]


printPolinom : Polinom -> Html Msg
printPolinom polinom =
    let
        members =
            List.map printPolinomMember polinom
    in
        div [] members


calculateView : Model -> Html Msg
calculateView model =
    if model.calculate then
        div []
            [ div [ class "nominator" ] [ printPolinom model.nominator ]
            , text " / "
            , div [ class "denominator" ] [ printPolinom model.denominator ]
            , text " = "
            , div [ class "division" ]
                [ printPolinom <| dividePolinoms model.nominator model.denominator ]
            ]
    else
        text ""


view : Model -> Html Msg
view model =
    div []
        [ div []
            [ text "Nominator"
            , input [ type_ "text", placeholder "x^2 + x^0", onInput InputNominator ] []
            ]
        , div []
            [ text "Denominator"
            , input [ type_ "text", placeholder "x^2 + x^0", onInput InputDenominator ] []
            ]
        , button [ onClick Calculate ] [ text "Calculate" ]
        , calculateView model
        ]



-- update


parsePolinom : String -> Polinom
parsePolinom nominator =
    let
        parsed =
            String.split " " nominator
                |> List.filterMap (Result.toMaybe << String.toInt)
    in
        List.reverse <| List.sortBy abs parsed


update : Msg -> Model -> Model
update msg model =
    case msg of
        InputNominator nominator ->
            { model | nominator = parsePolinom nominator, calculate = True }

        InputDenominator denominator ->
            { model | denominator = parsePolinom denominator, calculate = True }

        Calculate ->
            { model | calculate = True }

Нужно module Main exposing (..) если тестить на локальный машине или можно воспользоваться онлайн интерпретатором

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

(знаю что у меня тут грубые ошибки в английском, поэтому не судите строго)

Добавлено через 14 минут
Да, чуть не забыл, вот еще библиотека Elm тут можно подсмотреть какой вообще функционал стандартных модулей.

XRuZzz · 07.04.2018, 06:08

Ну Elm для Weba, а вам нужно свести деление полиномов к чистым функциям.

Сообщение от outoftime

dividePolinoms : Polinom -> Polinom -> Polinom
dividePolinoms nominator denominator = ...

Если в Elm нету Классов типов как в Haskell то по другому и не сделать. Поэтому остаётся делать на чистых функциях.
А в Haskell есть класс типов Fractional, чтобы перезгрузить оператор "/".
Можно сделать без класса типа Fractional, чтобы функция выглядела так "</>". можно посмотреть тут:
Бинарные операторы и унарный минус
Для парсинга строк, в ФП обычно используют Комбинаторные парсеры. Если не использовать библиотеку parsec, то свой парсер, будет урезанным подобием parsec.
Вот кстати парсер для Elm:
https://github.com/elm-communi... ombinators
Но например, тут https://math.semestr.ru/gauss/factor.php с парсингом заморачиваться не стали и правильно сделали...

Добавлено через 6 часов 0 минут

Вот, всю ночь писал 6-8 строчек кода и возможно есть ошибки

. Возможно когда нибудь перепишу по человечески:

Haskell

getStep :: [Int] -> [Int] -> [Int] -> Int -> Bool ->([Int],[Int])
getStep rest _ res n True = (res, rest)
getStep xss@(x:xs) yss@(y:ys) res_old dif_pow_old _ =
 let
    dif_pow = (length xss - length yss)
    tail_step_poli = map (*x) ys
    parts_xs = splitAt (length tail_step_poli) xs
    step_res = (dropWhile (==0) $ zipWith (\x y -> x - y) (fst parts_xs) tail_step_poli) ++ snd parts_xs
    zeros = replicate (dif_pow_old - dif_pow - 1) 0
    res = res_old ++ zeros ++ [x `div` y]
 in
-- trace ("STEP RES " ++ (show step_res) ++ "\n RES " ++ show res) $   -- Если нужно посмотреть что происходит на каждой итерации рекурсии
    if length step_res>= length yss then getStep step_res yss res dif_pow False else getStep step_res yss res dif_pow True

В elm-e есть аналогичные функции.

Для
-x⁵+x²+x
x²+1
Ответ:
Целая часть: - x³+ x + 1
Остаток: - 1

Bash

1
2
3

$ ghci
ghci> getStep [-1,0,0,1,1,0] [1,0,1] [] 0 False
([-1,0,1,1],[-1])

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

Я пытался использовать списки вроде вашего [-5 2 1], но мне кажется алгоритм для таких списков будет сложнее.

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
		1
	Деление полиномов на Elm 04.04.2018, 00:00. Показов 831. Ответов 1 Метки нет (Все метки) Есть функциональный язык `Elm` который транслируется в `Javascript` спасает от великого множества ошибок. Это действительно так, но это функциональный язык, а я, сколько себя помню пишу на императивных языках. Есть полином, где $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i = \{-1, 0, 1\}$ , который я просто представляю в виде списка `Int` где каждый элемент это степень со знаком, который соответсвует $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i$ или отсутсвует когда $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i = 0$ Другими словами, список `[-5 2 1]` это полином $https://www.cyberforum.ru/cgi-bin/latex.cgi?-x^5+x^2+x$ Вопрос как это реализовать на любом языке функциональном, не используя библиотек, так как я не знаю найду ли аналоги в Elm. Есть пример реализации на C++. Вот то что у меня есть сейчас Код import Html exposing (..) import Html.Attributes exposing (..) import Html.Events exposing (..) import List import String import Char import Tuple import Result main = beginnerProgram { model = model, view = view, update = update } -- model type alias Polinom = List Int type alias Model = { nominator : Polinom , denominator : Polinom , calculate : Bool } type Msg = InputNominator String \| InputDenominator String \| Calculate model : Model model = Model [] [] False dividePolinoms : Polinom -> Polinom -> Polinom dividePolinoms nominator denominator = if List.length nominator < List.length denominator then nominator else denominator -- views printPolinomMember : Int -> Html Msg printPolinomMember member = let sign = if member >= 0 then "+" else "-" in span [] [ text <\| sign ++ "x" , sup [] [ text <\| toString <\| abs member ] ] printPolinom : Polinom -> Html Msg printPolinom polinom = let members = List.map printPolinomMember polinom in div [] members calculateView : Model -> Html Msg calculateView model = if model.calculate then div [] [ div [ class "nominator" ] [ printPolinom model.nominator ] , text " / " , div [ class "denominator" ] [ printPolinom model.denominator ] , text " = " , div [ class "division" ] [ printPolinom <\| dividePolinoms model.nominator model.denominator ] ] else text "" view : Model -> Html Msg view model = div [] [ div [] [ text "Nominator" , input [ type_ "text", placeholder "x^2 + x^0", onInput InputNominator ] [] ] , div [] [ text "Denominator" , input [ type_ "text", placeholder "x^2 + x^0", onInput InputDenominator ] [] ] , button [ onClick Calculate ] [ text "Calculate" ] , calculateView model ] -- update parsePolinom : String -> Polinom parsePolinom nominator = let parsed = String.split " " nominator \|> List.filterMap (Result.toMaybe << String.toInt) in List.reverse <\| List.sortBy abs parsed update : Msg -> Model -> Model update msg model = case msg of InputNominator nominator -> { model \| nominator = parsePolinom nominator, calculate = True } InputDenominator denominator -> { model \| denominator = parsePolinom denominator, calculate = True } Calculate -> { model \| calculate = True } Нужно `module Main exposing (..)` если тестить на локальный машине или можно воспользоваться онлайн интерпретатором Буду признателен если дадите хотябы идею как это решить в функциоальном стиле. (знаю что у меня тут грубые ошибки в английском, поэтому не судите строго) Добавлено через 14 минут Да, чуть не забыл, вот еще библиотека Elm тут можно подсмотреть какой вообще функционал стандартных модулей. 0

	07.04.2018, 06:08