[haskell]问个求子串位置的程序

Question

本帖最后由 retuor 于 2010-07-16 12:40 编辑

做了个练习，大家给点意见。

Exercise 10. Write a function         f :: String -> String -> Maybe Int
that takes two strings. If the second string appears within the first, it
returns the index identifying where it starts. Indexes start from 0. For
example,
         f "abcde" "bc" ==> Just 1
         f "abcde" "fg" ==> Nothing

我的想法是，如果 s2 是 s1=(x:xs) 的前缀，则返回 0，否则返回 1+ s2 在 xs 中的位置，如是递归下去。由于题目要求返回 Maybe 类型，最好能有  (Just 1)+(Just 1)=Just 2 之类的运算，所以写了个 Maybe Int 的 instance.

2. instance (Num a)=> Num (Maybe a) where
3.     (Just n) + (Just m) = Just (n+m)
4.     _+_=Nothing                          
6. f [] s2=Nothing
7. f s1@(x:xs) s2 = if isPrefix s1 s2 then Just 0 else (Just 1)+ (f xs s2)
8.                  where
9.                    isPrefix _ [] = True
10.                    isPrefix (x:xs) (y:ys) = if x==y then isPrefix xs ys else False
11.                    isPrefix _ _ = False

复制代码

Answer 1

嘿嘿，再次学到，

2. f [] s2=Nothing
3. f s1@(x:xs) s2 = if isPrefix s1 s2 then Just 0 else (f xs s2)>>=return.(+1)
4.                  where
5.                    isPrefix _ [] = True
6.                    isPrefix (x:xs) (y:ys) = if x==y then isPrefix xs ys else False
7.                    isPrefix _ _ = False

复制代码

Answer 2

[code]fmap (+1) (f xs s2) [code]
换成
[code]f xs s2 >>= (x -> return (x+1))[code]
也是差不多

一个用的functor  一个用的是monad

还可以直接使用 pattern match
比如写个
maybeAdd Nothing _ = Nothing
maybeAdd _ Nothing = Nothing
maybeAdd (Just x) (Just y) = Just (x+y)

helper function 相对来说也比 实现 一个  instance 来实现(+)要好点吧。。。。

Answer 3

fmap 好，改过来了。

2. f [] s2=Nothing
3. f s1@(x:xs) s2 = if isPrefix s1 s2 then Just 0 else fmap (+1) (f xs s2)
4.                  where
5.                    isPrefix _ [] = True
6.                    isPrefix (x:xs) (y:ys) = if x==y then isPrefix xs ys else False
7.                    isPrefix _ _ = False

复制代码可读性那个也很有道理，不过暂时不改了。

有收获，谢谢啊。

Answer 4

再补充点
isPrefix s1 s2
一般如果是这种名字的函数写成
  s1 `isPrefix` s2  可读性是不是强点？

Answer 5

本帖最后由 SNYH 于 2010-07-17 20:16 编辑

2. else (Just 1)+ (f xs s2)
3. 可以改为
4. else  fmap (+1) (f xs s2)
5. 不需要instance
6. Maybe 是一个典型的functor

复制代码而且你实现的这个Num 的instance 不完全其他的几个方法没有实现会出现警告的

另外 isPrefix 在Data.List 中有一个对应的函数  Data.List.isPrefixOf