Haskell

 
0
 
Functional languages
ava
Vokunya | 26.03.2011, 15:29
Не буду врать о том, что пытался разобраться - потраченное время дороже. Надо сделать эти задачи и забыть все, как страшный сон  smile :

1. Дана последовательность символов  s1 , s2 , ..., sn (n>=2 и заранее неизвестно). Получить последовательность символов, содержащую только последние вхождения каждого символа в строку с сохранением  их исходного взаимного порядка.

2.  а) удалить из списка все повторяющиеся подсписки;  
     б) подсчитать количество положительных чисел в списке; 
     в) подсчитать сумму положительных и произведение отрицательных элементов списка; 
     г) подсчитать число повторяющихся элементов списка.

3. Подсчитать количество вхождений в дерево данной метки

4. Разработать программу для определения и вывода на экран неотрицательных значений функции f(x) = lg((m!)^3 – 1/n!)  . Значения n, m ввести с клавиатуры 


Если у кого есть наработки - буду благодарен, если кто готов взяться за решение, то пишите - договоримся


З. Ы. Модераторы, переместите пожалуйста в ветку Функциональные языки... только сейчас заметил, что есть такой раздел 
Comments (20)
ava
Void | 27.03.2011, 18:42 #
Решения в виде отдельной функции. Как там у вас принято ввод-вывод организовывать, неизвестно. Подразумевается import Data.List.
1.

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = reverse . nub . reverse

2.а. Непонятно условие, на входе список списков (тип Eq a => [[a]]) или плоский список, из которого надо выделять возможные подсписки? В последнем случае, если не ограничить длину подсписка снизу, получается странное.
2.б.

countPositive :: (Num a, Ord a) => [a] -> Int
countPositive = length . filter (> 0)

Можно без Ord, раздутость Num поможет:

countPositive :: Num a => [a] -> Int
countPositive = length . filter ((== 1) . signum)

2.в

calculateStuff :: (Num a, Ord a) => [a] -> (a, a)
calculateStuff s = (sum p, product n) where (p, n) = partition (>= 0) s

Аналогично 2.б, partition (>= 0) можно поменять на partition ((/= -1) . signum)
2.г.

duplicateCount :: Ord a => [a] -> Int
duplicateCount = length . filter ((> 1) . length) . group . sort

Или, если напрягает лишний констрейнт Ord, то только на списках и Eq с квадратичной сложностью:

duplicateCount :: Eq a => [a] -> Int
duplicateCount xs =
    traverse xs [] 0 where
        traverse [] set acc = acc
        traverse (x:xs) set acc
            | x `elem` set = traverse xs set (acc + 1)
            | otherwise = traverse xs (x:set) acc

3. Просто дерево?

data Tree a = Leaf a | Node a [Tree a]

count :: Eq a => a -> Tree a -> Int
count x (Leaf y) = fromEnum $ x == y
count x (Node y ys) = fromEnum (x == y) + (sum $ map (count x) ys)

{-
              alpha
              /  \
             /   gamma
           beta  /   \
               alpha delta
-}
tree = Node "alpha" [Leaf "beta", Node "gamma" [Leaf "alpha", Leaf "delta"]]

4. f(x), а где справа x? Выражение читать как lg((m!)^3 - (1/n!)) или lg(((m!)^3 - 1) / n!)? Что делать с отрицательными значениями функции?
ava
k0rvin | 28.03.2011, 12:36 #
Цитата (Void @ 27.3.2011,  18:42)
Выражение читать как lg((m!)^3 - (1/n!)) или lg(((m!)^3 - 1) / n!)?

эээ, вроде (-) всегда имел меньший приоритет, чем (/)
ava
Vokunya | 28.03.2011, 17:37 #
Собственно, раз пошла такая пьянка, то мне уже даже самому захотелось разобраться  smile 

По поводу
2а: на входе список списков, т.е. имеем, например [[1,2],[3,5,7],[1,8,1,9],[1,2],[1,2], [3,5,7]], получим [[1,2],[3,5,7],[1,8,1,9]]
Думаю, что здесь достаточно будет nub? Или я ошибаюсь? просто сейчас нет возможности проверить

2в: я очень прошу Void снабдить сие дело комментариями, или подскажи откуда это почитать

2г: а можно так? 

countItems item = length . filter (item==)


3. бинарное дерево, и если можно тоже комментов

4. 
Цитата
 f(x), а где справа x? Выражение читать как lg((m!)^3 - (1/n!)) или lg(((m!)^3 - 1) / n!)? Что делать с отрицательными значениями функции?


с X разберусь; читать как первый вариант, и по этой задаче я тоже кое-чего сам набрасал, только с ошибками не могу справиться ))
позже покажу код - осбудим
ava
Void | 28.03.2011, 19:30 #
Цитата (k0rvin @  28.3.2011,  14:36 findReferencedText)
эээ, вроде (-) всегда имел меньший приоритет, чем (/) 

Ну больно несоразмерные члены получались, захотелось убедиться, что это не ошибка небрежного копипаста.

Цитата (Vokunya @  28.3.2011,  19:37 findReferencedText)
2а: на входе список списков, т.е. имеем, например [[1,2],[3,5,7],[1,8,1,9],[1,2],[1,2], [3,5,7]], получим [[1,2],[3,5,7],[1,8,1,9]] 

Думаю, что здесь достаточно будет nub? Или я ошибаюсь? просто сейчас нет возможности проверить

Да, Eq a => Eq [a], т.е. если тип элемента списка реализует сравнение на равенство, то сравнение списков реализуется автоматически естественным образом.
Цитата (Vokunya @  28.3.2011,  19:37 findReferencedText)
2в: я очень прошу Void снабдить сие дело комментариями, или подскажи откуда это почитать

Гм, если предыдущие были понятны, то что в этой функции особенного? sumproductpartition. partition делит список на две части: соответствующие предикату и нет. Функции надо искать в Hoogle, он рулит.
Цитата (Vokunya @  28.3.2011,  19:37 findReferencedText)
3. бинарное дерево, и если можно тоже комментов

Не упорядоченное? Можно со списками оставить, можно новый тип специально для бинарного дерева состряпать:
data BinTree a = Node a (BinTree a) (BinTree a) | Leaf a

count :: Eq a => a -> BinTree a -> Int
count x (Leaf y)
    | x == y    = 1
    | otherwise = 0
count x (Node y l r)
    | x == y    = 1 + count x l + count x r
    | otherwise = count x l + count x r

tree = Node "alpha" (Leaf "alpha") (Node "beta" (Leaf "gamma") (Leaf "delta"))

main = print $ count "alpha" tree

Что конкретно прокомментировать? АДТ (алгебраический тип данных) понятен? Тип функции? К записи функции вопросы?
Просто создаётся впечатление, что некое знакомство с Haskell уже есть и объяснять всё с нуля не имеет смысла, но где именно проходит граница понимания, неясно.
Цитата (Vokunya @  28.3.2011,  19:37 findReferencedText)
позже покажу код - осбудим

Ждём.
ava
Vokunya | 30.03.2011, 21:02 #
Цитата


Просто создаётся впечатление, что некое знакомство с Haskell уже есть


Что вы, увольте ))) я даже на hаskell.org залез уже после того, как здесь тему создал )
Теперь по делу:

Задача 1: че-то код для символов не работает, а только для чисел. Потом, как организовать ввод n и ввод символов количества n, для которых потом применим эту функцию? могу сделать что-то такое

do putStrLn "Input N:"
          n <- readLn

а как потом n привести к числу (я же правильно понимаю, что сейчас это строка?)

read n::Int

вроде не работает... или я что-то не так делаю
и как потом организовать ввод списка элементов?
Теперь по комментам:

removeDuplicates = reverse . nub . reverse

Вот что это строчка делает? Словами можете рассказать? Для чего нужна "."? ну т.е reverse - перевернули список, а потом что с ним? )

Задача 3: 
Цитата


АДТ (алгебраический тип данных) понятен? Тип функции? К записи функции вопросы?


непонятно как вот это работает

count :: Eq a => a -> BinTree a -> Int
count x (Leaf y)
    | x == y    = 1
    | otherwise = 0
count x (Node y l r)
    | x == y    = 1 + count x l + count x r
    | otherwise = count x l + count x r

но пока не говорите )) я еще сам в коде поковыряюсь, потом, когда возникнут конкретные вопросы - дам знать... единственное, что значит знак "$" вот в этом?

main = print $ count "alpha" tree


Задача 4: здесь такие изменения в условии - это не функция, просто задаем m и n, устанавливаем диапазон их изменения и шак изменения - 1
вопросы остается как и для первой задачи: как ввести m, n, шаг и диапазон и как их привести к числовому типу... и напрашивается для реализации какой-нибудь while {}, но что-то мне подсказывает, что это совсем не "гуд" для функциональных языков... но что-то тяжко приспособится к новой парадигме )) поэтому промойте мне мозг, пожалуйста  smile 
ava
Void | 30.03.2011, 23:48 #
Цитата (Vokunya @  30.3.2011,  23:02 findReferencedText)
Вот что это строчка делает? Словами можете рассказать? Для чего нужна "."? ну т.е reverse - перевернули список, а потом что с ним? )

Точка — это композиция функций. Т.е. (f . g)(x) = f(g(x)). Нашу функцию можно записать развёрнуто:
removeDuplicates s = reverse (nub (reverse s))

nub удаляет из списка дублирующиеся элементы, но оставляет от каждого первое вхождение, а не последнее, как нам нужно. Поэтому мы сначала разворачиваем список, чтобы nub оставила последние вхождения, а потом переворачиваем результат обратно.
Цитата (Vokunya @  30.3.2011,  23:02 findReferencedText)
че-то код для символов не работает, а только для чисел.

Не понял. Для всего он работает, лишь бы равенство для этого типа было определено. Пример с ошибкой можно?

Цитата (Vokunya @  30.3.2011,  23:02 findReferencedText)
Потом, как организовать ввод n и ввод символов количества n, для которых потом применим эту функцию? могу сделать что-то такое

readLn читает сразу в нужном типе (какой выведет из контекста или явно указанный):
do
    n <- readLn :: IO Int

Но направление мысли с read тоже правильное. Для того чтобы считать строку без обработки в System.IO есть getLine:
do
    s <- getLine
    let n = read s :: Int

Дальше, что есть символ в условиях задачи? char? В таком случае вводить число символов, а потом ещё вводить их по одному выглядит издевательством над пользователем. Строка в Haskell — уже список символов (тип [Char]). Но для иллюстрации, пожалуйста, ввод n и списка длиной n, обобщённый в виде функции:
inputList :: Read a => String -> IO [a]
inputList prompt = do
    putStrLn prompt
    n <- readLn :: IO Int
    replicateM n readLn

main = do
    myList <- inputList "Enter N" :: IO [Int]
    print myList

replicateM живёт в Control.Monad. Эта фукнция берёт монадическое действие, повторяет его n раз и возвращает собранные результаты в виде списка. Увы, ввод-вывод в Haskell неразрывно связан с монадами, и объяснять их в одном посте я не возьмусь. Конкретно монада IO инкапсулирует в себе все вычисления с побочными эффектами, и вырвать результат такого вычисления из неё невозможно. IO a — это действие с побочными эффектами, приводящее к вычислению значения типа a.
Цитата (Vokunya @  30.3.2011,  23:02 findReferencedText)
единственное, что значит знак "$" вот в этом?

$ — это оператор применения функции. f $ x = f(x). Из-за правой ассоциативности и минимального приоритета он позволяет экономить скобки в цепочке вызовов: f $ g $ h x эквивалентно f(g(h(x))).
Цитата (Vokunya @  30.3.2011,  23:02 findReferencedText)
Задача 4: здесь такие изменения в условии - это не функция, просто задаем m и n, устанавливаем диапазон их изменения и шак изменения - 1

вопросы остается как и для первой задачи: как ввести m, n, шаг и диапазон и как их привести к числовому типу... и напрашивается для реализации какой-нибудь while {}, но что-то мне подсказывает, что это совсем не "гуд" для функциональных языков... но что-то тяжко приспособится к новой парадигме )) поэтому промойте мне мозг, пожалуйста  smile 


В общем случае цикл в функциональном языке превращается в рекурсию. Но, как правило, рекурсия — слишком примитивный инструмент и вместо неё можно использовать заготовленные в языке и библиотеках абстракции. В Haskell цикл очень часто превращается в «построй список и что-то сделай с его элементами». Куча функций [высшего порядка] есть для того чтобы списки строить и преобразовывать.
Для конкретного случая целых чисел есть очень удобный синтаксис: [m..n] — это список от m до n с шагом 1. (Это работает не только для чисел, но и для любых типов, реализующих класс Enum).
Применить функцию к каждому элементу списка можно с помощью map: map f [a1, a2, ... an] = [f(a1), f(a2), ... f(an)]. В случае функции двух аргументов запись получается тяжеловесная:
map (\x -> map (\y -> f x y) [1..10]) [1..10]

К счастью, в Haskell есть синтаксический сахарок как раз для таких случаев — list comprehensions. Предыдущая запись с ними превращается в
[f x y | x <- [1..10], y <- [1..10]]

Разница в том, что list comprehensions результирующий список сливают, делают плоским. При использовании map получился бы список списков.
Следующий вопрос: нам функцию нужно не просто вычислить, а вывести, табулировать. Можно затащить вывод внутрь comprehension, получит на выходе [IO a] (список действий вывода) и актуализировать его с помощью sequence_ из Control.Monad:
sequence_ [printf "f(%d, %d) = %d\n" x y (f x y) | x <- [1..10], y <- [1..10]]

Подчёркивание в конце функции, как правило, обозначает, что она выкидывает результат, т.е. выполняется только ради побочных действий и возвращает IO (). printf живёт в Text.Printf.
Можно наоборот, вытащить наружу аргументы вместе с результатами (в виде кортежа) и применить к ним вывод:
forM_ [(x, y, f(x y)) | x <- [1..10], y <- [1..10]] $ \(x, y, r) -> printf "f(%d, %d) = %d\n"

forM живёт в Control.Monad. Собственно, название функции намекает. С ней можно сделать совсем похоже на императивный цикл:
forM_ [1..10] $ \i ->
    forM_ [1..10] $ \j -> do
        let result = f i j
        printf "f(%d, %d) = %d\n" i j result
ava
Vokunya | 03.04.2011, 14:00 #
Цитата


Не понял. Для всего он работает, лишь бы равенство для этого типа было определено. Пример с ошибкой можно?




removeDuplicates [a,b,c,a,b] 
ERROR - Undefined variable "a"   


Код такой:

module Task_1 where
import List

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = reverse . nub . reverse
ava
Void | 03.04.2011, 14:51 #
Цитата (Vokunya @  3.4.2011,  16:00 findReferencedText)
removeDuplicates [a,b,c,a,b] 

ERROR - Undefined variable "a"   

Хаскель — это не Лисп всё-таки smile «Символов» в таком смысле в нём нет. Значение должно иметь какой-то тип. Я всю дорогу под символами подразумевал Char:
> removeDuplicates ['a', 'b', 'c', 'a', 'b']
"cab"
> removeDuplicates "abcab"
"cab"


Можно даже так:
data Symbol = A | B | C deriving Eq

removeDuplicates [A, B, C, A, B]
ava
Vokunya | 03.04.2011, 23:11 #

> removeDuplicates ['a', 'b', 'c', 'a', 'b']

мдя... что-то я совсем затупил ((
выходные плохо влияют на работу мозга ))
ava
Vokunya | 18.04.2011, 22:08 #
Меня убивает 4-ая задача...

module Task_4 where
import Monad
import List

factorial n = if n == 0 then 1 else n * factorial (n - 1)
l = logBase 10 l

inputN = do
    n <- readLn :: IO Int
    print n

inputM = do
    m <- readLn :: IO Int
    print m

inputSteps = do
    steps <- readLn:: IO Int
    print steps

forM_ [n..n+steps] $ \i ->
    forM_ [m..m+steps] $ \j -> do
        let result = f i j
        printf "f(%d, %d) = %d\n" i j result



Syntax error in module definition (unexpected `..')   


и в forM_ прокатит ли [n..n+steps]?
ava
Void | 19.04.2011, 11:30 #
Тут проблемы со структурой программы. Получился несвязанный набор объявлений, никем не используемых. Выражения на верхнем уровне недопустимы, только объявления. В Haskell, как и в ряде «обычных» языков, точка входа в программу называется main. Эта функция должна иметь тип IO a (Как правило, просто IO (), потому что возвращаемое значение нигде не используется. Код возврата программы можно установить с помощью функций из модуля System.Exit). Кроме того, если модуль не безымянный, и не называется Main, то GHC надо явно указать, в каком модуле находится точка входа с помощью опции -main-is:
ghc --make -main-is Task_4 Task_4.hs -o task_4

Соответственно, код будет выглядеть примерно так:
module Task_4 where

import Control.Monad
import Text.Printf

...

main = do
    n <- readLn :: IO Int
    m <- readLn :: IO Int
    steps <- readLn :: IO Int
    forM_ [n..n+steps] $ \i ->
        forM_ [m..m+steps] $ \j -> do
            let result = f i j
            printf "f(%d, %d) = %d\n" i j result

И ещё, смысл вот этого объявления до меня не доходит:
Цитата (Vokunya @  19.4.2011,  00:08 findReferencedText)
l = logBase 10 l
ava
Shaggie | 23.04.2011, 03:16 #
Цитата (Vokunya @  18.4.2011,  23:08 findReferencedText)
forM_ [n..n+steps] $ \i ->
  forM_ [m..m+steps] $ \j -> do
    let result = f i j
    printf "f(%d, %d) = %d\n" i j result

Неудачная запись для хаскеля. Теперь ещё отрицательные значения отсекать придётся отдельным условием на каждом шаге. Лучше получить все результаты одним списком, а потом обработать:


let res = [f i j | i <- [m..m+steps],
                   j <- [n..n+steps]]
mapM_ (printf "%f\n") $ filter (>= 0) res


Если нужна отладочная запись, можно собрать результаты в тупл (пример ниже) или, для удобства, завести отдельный рекорд


logDebugRes (i, j, f) = printf "f(%d, %d) = %f\n" i j f
positiveRes (_, _, f) = f >= 0

main = do
...
let res = [(i, j, f i j) | i <- [m..m+steps],
                           j <- [n..n+steps]]
mapM_ (logDebugRes) $ filter (positiveRes) res
ava
Vokunya | 23.04.2011, 16:15 #

module Task_4 where

import Monad
import Text.Printf

factorial n = if n == 0 then 1 else n * factorial (n - 1)

my a b = logBase 10 ((factorial a)^3 - 1/(factorial b))

main = do
    n <- readLn :: IO Int
    m <- readLn :: IO Int
    steps <- readLn :: IO Int
    let res = [my i j | i <- [m..m+steps], j <- [n..n+steps]]
    mapM_ (printf "%f\n") $ filter (>= 0) res

Выдает:
test.hs:14:16:
    No instance for (Floating Int)
      arising from a use of `my'
    Possible fix: add an instance declaration for (Floating Int)
    In the expression: my i j
    In the expression:
      [my i j | i <- [m .. m + steps], j <- [n .. n + steps]]
    In an equation for `res':
        res = [my i j | i <- [m .. m + steps], j <- [n .. n + steps]]

Читал про то, что вроде как надо использовать fromIntegral  и floor, но не помогло, но скорее всего я не так что-то делал

А если поменять на простую функцию, например:

my a b = a+b

то *** Exception: Printf.printf: bad argument (вводил значения 3 2 1)
ava
Void | 23.04.2011, 16:28 #
Цитата (Vokunya @  23.4.2011,  18:15 findReferencedText)
Читал про то, что вроде как надо использовать fromIntegral  и floor, но не помогло, но скорее всего я не так что-то делал

Можно fromIntegral или realToFrac:
my (fromIntegral i) (fromIntegral j) ...
Но тогда возникнет ещё одна ошибка из-за того, что конкретный тип возвращаемого значения my не определён и не выводится из констрейнтов. Обходится явной декларацией типа my:
my :: Double -> Double -> Double
В таком виде всё работает.

Цитата (Vokunya @  23.4.2011,  18:15 findReferencedText)
то *** Exception: Printf.printf: bad argument (вводил значения 3 2 1)

%f требует вещественного аргумента. При my a b = a + b все типы выводились как целые. Вот, кстати, проблема printf: убивает типизацию.
ava
Shaggie | 23.04.2011, 21:41 #
Vokunya, можно создать собственный конвертер интов во флоаты со строгим приведением типа

iToF n = (fromIntegral n) :: Float

тогда my (iToF i) (iToF j) отработает безошибочно.
ava
Vokunya | 12.05.2011, 20:21 #
Void, Shaggie, спасибо огромное - заработало.  smile 
Тему пока не закрываю - могут еще возникнуть вопросы.

А вот и вопросы, не заставили себя долго ждать  smile 

7 //n
5 //m
2 //steps

//результат вычислений
6.237543738093008
6.237543738136641
6.237543738142182
8.571997489293574
8.571997489293777
8.571997489293802
11.107291609336576
11.107291609336576


На каждой итерации результат вычислений заносится в res, мы и получили 3 значения, но которые продублировались. Отчего такое поведение?
ava
Void | 16.05.2011, 22:48 #
Цитата (Vokunya @  12.5.2011,  22:21 findReferencedText)
На каждой итерации результат вычислений заносится в res, мы и получили 3 значения, но которые продублировались. Отчего такое поведение?

Почему 3?
m = 7, 8, 9
n = 5, 6, 7
Итого 9 комбинаций.
А значения не дублируются, просто 1/b! << (a!)^3 и изменение n влияет очень слабо.
ava
Vokunya | 17.05.2011, 00:12 #
Хм. Просто я ожидал, что логика работы будет следующей:

1-ая итерация : m = 7, n = 5
2-ая итерация : m = 8, n = 6
3-ая итерация : m = 9, n = 7
ava
Shaggie | 23.05.2011, 02:30 #
Цитата (Vokunya @  17.5.2011,  01:12 findReferencedText)
1-ая итерация : m = 7, n = 5

2-ая итерация : m = 8, n = 6

3-ая итерация : m = 9, n = 7 

Ха, немножко промахнулся. Увидел лесенку форов и соптимизировал в list comprehension. Итог одинаков - декартово произведение множеств.

Ну так это несложно переделать. Что по сути надо? Получить два списка [7,8,9] и [5,6,7] и работать с попарно склеенными элементами [(7,5),(8,6),(9,7)]. Даже более того, можно создать два бесконечных списка чисел и бесконечно их склеивать, никаких проблем. Потенциально бесконечно (Волшебная Супер Сила Хаскеля!)
Создать бесконечный список возрастающих чисел:

-- вариант 1, Prelude
iterate succ n
-- вариант 2, сахар
[n..]

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

Итого:

let res = [my i j | (i,j) <- take (steps + 1) $ zip [m..] [n..]]
ava
Vokunya | 02.06.2011, 14:02 #
Со всем разобрался.
Огромное спасибо за помощь
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Void   Shaggie   Vokunya   k0rvin
advanced
Submit